まず Manachar のアルゴリズムで各文字からの回文半径を求めておきます。

\(T\) に対する問題を考えましょう。prefix が切り取られることによって解は増加しないので、greedy に前から切っていくアルゴリズムが正当です。 とくに、\(T[i-k,...,i,...,i+k]\) が極大な回文なとき \(i-k\) から \(i\) に辺を張り、各 index \(j\) に対して \(j\) から \(j-1\) に辺を張ったグラフを考えれば、 答えは \(|T|+1\) から、このグラフ上で \(1\) から到達できる頂点の番号の最大値を引いたものになります。

\(S\) に対する問題を考えましょう。\(j\) を 1 ずつ増やしながら、\(S[i,...,j]\) に対する問題をすべての \(i\) に対して同時に解くことを繰返します。

\(S[1,...,j]\) に対し、上記のグラフ上で \(i\) から到達できる頂点番号の最大値を \(f_j(i)\) とします。すると各 \(k\) に対し、\(f_j(i)=k\) なる \(i\) の集合は、\(k\) で終わるなんらかの区間になります。 これらの区間を順に \([1=x_0,...,x_1-1],[x_1,...,x_2-1],...,[x_{t_j-1},...,x_{t_j}-1=j]\) としましょう。 \(j\) を増やす操作に対してこれらの区間を高速で管理できれば問題は解けます。

\(j\) を増やすことによって区間が分割されることはありません。統合されることはありますが、統合はならし \(O(1)\) 回しか起きないので、統合イベントを全部列挙できればよいです。 区間 \(I\) が次の区間と統合されるのは、\(I\) 内で始まって \(I\) 外に中心を持ち、\(j+1\) で終わる回文が存在するときです。 それ以前に統合されていないという条件より、\(I\) の終端で始まって \(j+1\) で終わる回文のみ考えれば十分です。

区間 \(J\) を\([1,...,j-1]\) で初期化し、Manachar のアルゴリズムで求めた列を使って \(J\) 内で始まって \(j+1\) で終わる回文の中でもっとも後ろで始まるものを探し、 それは区間を統合することが保証できるので統合し、\(J\) を適切に更新、ということを繰返すことで、 区間の統合イベントはイベント発生回数に比例する計算量で全部列挙できます。 イベントの列挙は、極大回文の終端 index を持たせた配列を sparse table に載せて二分探索をするなどの手段で高速に実現可能です。 よって O(|S| log |S|) 時間でこの問題が解けます。