一見すると指数時間かかりそうな問題で、実際片側から文字列を作っていくと、無限の可能性があって上手く求めることができません。

例えば、ある文字列が回文であることを判定するには、外側から対応している文字が一致していれば取り除き、途中で一致していなければ否定することで判定できます。

上の方法では、事前に全体の文字列の長さを知る必要がなく、この方法を活かすことを考えてみましょう。

回文の「左右」の部分から文字列を構成することを考えます。まず、初めは左右とも空です。

途中の状態に左右のどちらかに与えられた文字列のどれかを繋げる遷移を考えます。このとき、まだマッチしていない部分と整合しない場合は、その遷移はできません。

この方法で伸ばしていくと、回文でないような部分だけを保持することができますが、まだ無限状態あります。

ここで、文字列が余っている部分の反対側にのみ文字列を追加するような遷移に限定することを考えます。すると、余っている文字列というのは、与えられた文字列のいずれかのprefix/suffixに現れるものであることがわかります。

よって、余りの文字列を \(2N \max |S_i|\) 通りに限定することができたので、これらの文字列を頂点とみなし、各遷移のコストを \(C_i\)としてDijkstra法などで空文字列/回文までの距離の最小値を求めればよいです。この時間計算量は、比較などを愚直にやっても 、\(L:= \max |S|\) として\(\mathrm{O}(N^2 L (L + \log NL))\) となり十分高速です。

実装例(C++)