Manacher のアルゴリズム PHP編（paizaランク B 相当）

前回まで、回文の性質を利用した効率的な最長回文半径の計算方法について学んできました。これを利用して、各中心について回文の性質を利用して最長回文半径を効率的に更新していけば、最長回文半径を高速に求めることができます。このように、回文の性質を利用して時間計算量 O(|s|) で計算するアルゴリズムを Manacher のアルゴリズムといいます。

では、実際に Manacher のアルゴリズムを実装してみましょう。
最長回文半径 p[i] を求める単純なアルゴリズムは、以下のようなものでした。

for i = 0 から |s| - 1 まで:
    while 0 <= i - p[i] かつ i + p[i] < |s| かつ s[i - p[i]] == s[i + p[i]]: 
        p[i]++;

ここで、各最長回文半径を求める際に、今まで見た最長回文の右端の中で最も右にあるものをフロンティア、右端が最も右にある最長回文をフロンティアの最長回文と呼ぶことにします。すると、Manacher のアルゴリズムは、

1. もしフロンティアの回文が i 番目の文字を覆っていれば、フロンティアの最長回文をもとに、回文の性質を使って暫定的な最長回文半径を求める
2. もし、今見ている最長回文の右端がフロンティアの位置に一致している場合のみ、最長回文半径を再計算してフロンティアを更新する

という非常にシンプルなアルゴリズムになります。

具体的な疑似コードは以下のようになります。ここで、j はフロンティアの回文の中心の位置を表します。

j = 0
for i = 0 から |s| - 1 まで:
    if i < j + p[j]:
        p[i] = min(p[j - (i - j)], j + p[j] - i)
    if j + p[j] <= i + p[i]:
        while 0 <= i - p[i] かつ i + p[i] < |s| かつ s[i - p[i]] == s[i + p[i]]: 
            p[i]++;
        j = i

では、Manacher のアルゴリズムを実装してみましょう。
文字列 s が与えられます。このとき、s の 1, 2, 3, ..., |s| 番目の文字を中心としたときの最長回文半径を求めてください。
なお、文字を中心とする最長回文半径とは、その文字を中心とする回文の最大の長さを n としたとき、(n + 1) / 2 のことを言います。