まずはローリングハッシュと二分探索を使って 位置 \(i\) を中心とする回文の最大の長さを求める. 回文の長さが奇数の場合は位置 \(i\) が中心であり, 偶数の場合は位置 \(i, i+1\) が中心となる.

次に削除する文字を考える. 区間 \([l, r]\) で回文になっているとし, 削除する文字の位置を \(j\) とし, まずは左側だけを考える.

\(j \lt l-1\) のときは元の回文とはかすりもしてないので最大の長さは変わらない.

\(j = l-1\) のときは \(j\) の位置を削除することで回文がどれだけ伸ばせるかをやはりローリングハッシュと二分探索で求める.

\(l \leq j \lt i\) のときは, 回文の長さを長くするためにはは \([l-1, j]\) の区間の文字はすべて同じでなければならず, これは \(j = l-1\) の文字を削除する場合に帰結できるので考えなくてもいい.

\(j = i\) (回文の長さが偶数のときは \(j = i + 1\) も) の場合は \((\text{元の回文の長さ}) - 1\) が新しい回文の長さとなる.

以上をすべての \(i\) について調べる.