Codeforces Round #427 D. Palindromic characteristics
自然数kについて、k-palindromeを次の用に再帰的に定義する。
- 長さ1の文字は1-palindromeである。
- 文字列がk-palindrome ⇔ 文字列が回文になっている、かつ文字列の左半分(つまり右半分も)が(k-1)-palindromeである。
ただし、文字列の左半分とは長さ=[文字列の長さ/2]のプレフィックスのことである。
文字列sが与えられるので、次の長さ|s|の数列を作成せよ。
(sの部分文字列の中で1-palindromeの数, sの部分文字列の中で2-palindromeの数, ...)
定義どおりk-palindromeのkを再帰的に求める。文字列が回文でかつ、半分に割ってdfsした結果がk-1であれば、その文字列はk-palindromeになる。この結果をmemo[left][right]というテーブルでメモ化する。つまり、文字列の[left, right)に当たる部分文字列のkを入れていく。この時、回文判定をO(N)でやってしまうと、全体でO(N^3)かかり間に合わない。そこで、sとsの反転をつなげた文字列のローリングハッシュを作成しておき、回文判定をO(1)で行えるようにしておく。すると全体計算量がO(N^2)になり間に合う。
