Manacher's algorithm

my wikiに書いたものを貼り付けてみるテスト。htmlそのまま貼り付けられるけれど、互換性無いから手直ししないとだめだね。

アルゴリズム

「回文の中心」を考えるために、奇回文のみを考える。 偶回文に対応するために、文字列の間になんでもいいダミーの文字を挟む。 例えば、"abcb"を"a#b#c#b"とする。 すると、ダミー文字が中心の回文が偶回文に対応する。

文字列を左から見ていく。 今までで見つけた回文の中で、右端が最も右にあるものを記録しておく。

記録した回文に含まれている部分までは、現在の位置と対称的な位置にあるすでに求めた回文半径だけ一致している。 記録した回文に含まれていない不明な部分は普通に文字列をループで比較して伸ばせる。これを繰り返す。

最初にダミー文字を挟んだが、そのせいで、その文字列で回分半径を求めた結果は元の文字列の回文直径となっている。

なぜ線形時間か

内側のループは記録した右端から始まる。 また、右端以降がマッチしたとしたら今の回文が新たに記録され、右端も更新される。 ここで、記録された右端は一定方向にしか動かない。かつ、内側のループは、最大でも右端が動いた距離+1回しか回らない。 そのため右端でバウンドできる。右端が最大でもΘ(n)であることから、計算量はΘ(n)となる。