Day 104-Q4 | Manacher's Algorithm（最長回文部分文字列）

問題

英小文字からなる文字列$S$（$1\le|S|\le5\times10^5$）が与えられる。$S$の連続する部分文字列のうち回文になっているものの中で最長のものの長さを求めよ。

各中心について愚直に両側へ広げると$O(N^2)$。Manacher's Algorithmは、すでに計算済みの回文半径の対称性を利用して新しい中心の回文半径の下界を$O(1)$で見積もり、必要な分だけ広げることで、ならし$O(N)$で計算する。偶数長の回文も扱うため、文字の間と両端に区切り文字`#`を挿入した文字列に変換してから処理する。

入力形式

制約

$S$は英小文字のみ

$1 \le |S| \le 5\times10^5$

入出力例

入力例1

babad

出力例1

"bab"や"aba"が長さ3の回文部分文字列で最長。

入力例2

cbbd

出力例2

"bb"が長さ2の回文部分文字列で最長。

概念図: 変換文字列と回文半径

ヒント（段階的開示）

ヒント1: 方向性

各中心を愚直に広げるのは$O(N^2)$。ある中心の回文半径が分かっているとき、その内側にある別の中心の回文半径は、対称な位置の回文半径と多くの場合一致するはずである。この「既知の情報の再利用」が高速化の鍵。

ヒント2: アプローチ

文字の間と両端に`#`を挿入した文字列$T$を作り奇数長・偶数長を統一的に扱う。現在の「最も右まで広がっている回文」の中心`center`と右端`right`を管理し、新しい中心$i$の鏡像`mirror=2*center-i`の回文半径を初期値にして、そこからさらに愚直に広げる。

ヒント3: 誘導（コード骨格）

def manacher(s):
    t = '^#' + '#'.join(s) + '#$'
    n = len(t)
    p = [0] * n
    center = right = 0
    for i in range(1, n - 1):
        mirror = 2 * center - i
        if i < right:
            p[i] = min(right - i, p[mirror])
        while t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1
        if i + p[i] > right:
            center, right = i, i + p[i]
    return max(p)

模範解答 (Python)

import sys


def manacher(s):
    t = '^#' + '#'.join(s) + '#$'
    n = len(t)
    p = [0] * n
    center = 0
    right = 0
    for i in range(1, n - 1):
        mirror = 2 * center - i
        if i < right:
            p[i] = min(right - i, p[mirror])
        while t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1
        if i + p[i] > right:
            center, right = i, i + p[i]
    return max(p)


def solve():
    s = sys.stdin.readline().strip()
    print(manacher(s))


solve()

計算量: ならし $O(N)$。"babad"→3、"cbbd"→2 を確認済み。

Step-by-Step 解説

1文字列の変換
奇数長・偶数長を統一的に扱うため`#`を各文字の間・両端に挿入し、境界チェック省略のため番兵`^`,`$`を置く。

2対称性を利用した初期値の設定
`i < right`なら鏡像位置`mirror`の回文半径を参考に`p[i]=min(right-i, p[mirror])`とする。

3愚直な拡張
初期値から実際に一致するか両側に広げる。`right`は単調増加するため拡張の総コストは全体で$O(N)$。

4最大値の取得
すべての中心の$p[i]$の最大値が、元の文字列上での最長回文部分文字列の長さに一致する。

よくあるミス

ミス	原因	正しい書き方
偶数長の回文を見落とす	中心が文字の間にもあることを考慮していない	`#`を挿入して奇数長・偶数長を統一的に扱う
番兵なしで配列外参照(IndexError)を起こす	拡張ループの境界チェックを個別実装しようとして煩雑になる	両端に絶対一致しない`^`,`$`を置き範囲チェックを省略する
`p[i]`の初期値を常に0にする	対称性を利用する部分を実装し忘れている	`if i < right: p[i] = min(right-i, p[mirror])`を必ず入れる
`center, right`の更新条件を誤る	正しさ自体は保たれても計算量が悪化する	`i + p[i] > right`のときだけ更新する

次のステップ

発展: 相異なる回文部分文字列の個数を数える問題（Eertree／回文木との関連）
発展: 最長回文「部分列」（連続でなくてよい）は別のDP問題であることに注意し混同しない
次回予告: 最小費用流（MCMF）による割当問題への応用

自己評価

完全理解おおむね理解要復習

Day 104-Q4 — Manacher's Algorithm

問題