Count Unique Palindrome

この問題を解くうえでは以下の事実が重要になります。

• 長さが $N$ の文字列における連続する部分列において、現れる回文の種類数は高々 $N$ 種類である。

上記の事実を用いると、この問題は以下のような手順で解くことができます。

$1.$ Manacher's Algorithm を用いて各位置の最長回文半径 $r$ を求める。

$2.$ $r$ について降順に探索する。連想配列と Rolling Hash を用いて、ハッシュごとの個数を記録する。

• $r = 1$ の場合 ... 探索を終了する。
• それ以外の場合は続けて $r - 1$ について探索を行うが、$r$ についての回文の両端を削ると $r - 1$ についての回文が現れるため、それについても記録する。

上記の手順により、それぞれの回文の出現回数が分かり、このアルゴリズムは連想配列に C++ の map などを用いると $O(N \log N)$ で動作するためこの問題を高速に解くことができました。

追記: Palindromic Tree を用いることによってそのままこの問題を解くことができるようです。

初めの命題の証明

$1.$ 文字列の長さが $1$ の場合

現れる回文の種類数は $1$ 種類である。

$2.$ 末尾に文字を追加した場合に、新たに現れる回文の種類数が高々 $1$ 種類であることを示す。

文字列に新たに文字を追加した場合に新たに現れる回文は、末尾を端とする回文になる。
ここで、回文が $2$ 種類増えると仮定すると、長さが大きい方の回文に必ず長さ小さい方の回文が連続する部分列として含まれるため矛盾する。