問題
文字列 $S$ が与えられる。$S$ の最長回文部分文字列の長さを求めよ。
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $|S|$ | $1 \le |S| \le 5 \times 10^5$ | 文字列長 |
| 文字種 | 英小文字のみ | $|\Sigma| = 26$ |
入出力例
入力例1
abaaba出力例1
6入力例2
babad出力例2
3例1は文字列全体が回文。例2は bab または aba（長さ3）が最長。
概念図: 既知区間 $[l,r]$ の鏡写しトリック
ヒント
ヒント1（方向性）
各中心から左右に伸ばす愚直法は $O(N^2)$。すでに確定した回文の情報を対称な位置に「鏡写し」で使い回せないか考える。
ヒント2（アプローチ）
# 区切りで奇数長・偶数長を統一し、既知の最も右まで届く回文区間 $[l,r]$ を管理。$i \le r$ なら鏡像位置 $l+r-i$ の半径がヒントになり、$r$ が単調増加するため全体 $O(N)$。
ヒント3（ほぼ答え）
def manacher(t):
n = len(t)
p = [0] * n
l, r = 0, -1
for i in range(n):
k = 1 if i > r else min(p[l + r - i], r - i + 1)
while i - k >= 0 and i + k < n and t[i - k] == t[i + k]:
k += 1
p[i] = k - 1
if i + k - 1 > r:
l, r = i - k + 1, i + k - 1
return p模範解答
import sys
def manacher(t):
n = len(t)
p = [0] * n
l, r = 0, -1
for i in range(n):
k = 1 if i > r else min(p[l + r - i], r - i + 1)
while i - k >= 0 and i + k < n and t[i - k] == t[i + k]:
k += 1
p[i] = k - 1
if i + k - 1 > r:
l, r = i - k + 1, i + k - 1
return p
def solve():
s = sys.stdin.readline().strip()
t = '#' + '#'.join(s) + '#'
p = manacher(t)
print(max(p))
solve()計算量: $O(N)$（右端 $r$ が単調増加するため while の総実行回数は amortized $O(N)$）。
Step-by-Step 解説
Step 1: 変換文字列の構築
# を各文字の間・両端に挿入すると、すべての回文が「奇数長」になり場合分けが不要。境界外参照は i-k>=0 and i+k<n の明示的な範囲チェックで防ぐ（番兵文字は不要）。
Step 2: 既知区間 $[l, r]$ の管理
これまでに見つかった回文のうち右端が最も右まで届くものの区間を $[l, r]$ とする。$i \le r$ なら鏡像位置 $l+r-i$ の半径 p[l+r-i] がヒントになる。
Step 3: 鏡写しによる初期値
| 条件 | 初期値 $k$ |
|---|---|
| $i > r$（未探索領域） | $k=1$ から愚直拡張 |
| $i \le r$ | $\min(p[l+r-i],\ r-i+1)$ から拡張再開 |
Step 4: 区間更新と答えの集計
拡張後 $i+k-1 > r$ なら $(l,r)$ を更新。p 配列の最大値がそのまま元の文字列での最長回文長になる。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 番兵方式で右端が範囲外参照 | 単一の番兵だけでは最後の中心で配列外に出ることがある | i-k>=0 and i+k<n を明示的にチェック |
# 区切りを忘れる | 奇数/偶数長の場合分けが必要になり複雑化 | # 区切りで統一表現にする |
max(p) を2で割るなど余計な変換 | 変換文字列の半径がそのまま元の長さになる仕組みを誤解 | # 挿入方式では max(p) がそのまま答え |
次のステップ
- 発展問題: 全ての回文部分文字列の個数（$\sum (p[i]+1)//2$ で集計）
- 発展問題: Eertree（回文木）との比較・使い分け（動的追加が必要な場合は Eertree）
自己評価
理解度: / /
自分の回答:
気づき・メモ: