問題
長さ $N$ の文字列 $S$（英小文字）が与えられる。$Q$ 個のクエリに答えよ：
クエリ l r：$S[l..r]$（1-indexed）の部分文字列の中で、長さが最大の回文部分文字列の長さを求めよ。
制約
$1 \le N \le 3 \times 10^5$
$1 \le Q \le 10^5$
$1 \le l \le r \le N$
時間制限: 3秒
入出力例
入力例 1
10 3
abacabadab
1 10
3 8
5 7出力例 1
7
5
3概念図: ローリングハッシュ二分探索での回文判定
ヒント（段階的開示）
ヒント1: 方向性
各クエリ $[l,r]$ で最長回文部分列を求めたい。Eertree（回文オートマトン）は任意区間クエリには不向き。ローリングハッシュ + 二分探索で中心ごとに最長回文半径を $O(\log N)$ で求め、クエリ範囲内に収まる最大のものを返す戦略を考えましょう。
ヒント2: アプローチ
- 前処理: 各位置 $c$（奇数長・偶数長）について、最長回文半径 $R[c]$ をローリングハッシュ二分探索で $O(\log N)$ ずつ計算 → 全体 $O(N \log N)$
- 二重ハッシュ（$2^{61}-1$ と $2^{31}-1$ の Mersenne 素数）で衝突を防ぐ
- クエリ $[l,r]$: 各中心 $c$ について有効半径 $\min(R[c], c-l, r-c)$ を計算 → 最大値を返す
ヒント3: is_pal の実装
def is_pal(l, r):
# 前向きハッシュ [l..r] と 逆向きハッシュ [n-1-r..n-1-l] を比較
h1 = (hf1[r+1] - hf1[l] * pf1[r-l+1]) % MOD1
r1 = (sr1[n-r] - sr1[n-r + (r-l+1)] * pr1[r-l+1]) % MOD1 # 調整
if h1 != r1: return False
h2 = (hf2[r+1] - hf2[l] * pf2[r-l+1]) % MOD2
r2 = (sr2[n-r] - sr2[n-r + (r-l+1)] * pr2[r-l+1]) % MOD2
return h2 == r2模範解答 (Python)
import sys
input = sys.stdin.readline
def solve():
N, Q = map(int, input().split())
S = input().strip()
n = len(S)
MOD1, BASE1 = (1 << 61) - 1, 131
MOD2, BASE2 = (1 << 31) - 1, 137
def build_hash(s, base, mod):
h = [0] * (len(s) + 1)
pw = [1] * (len(s) + 1)
for i, c in enumerate(s):
h[i+1] = (h[i] * base + ord(c)) % mod
pw[i+1] = pw[i] * base % mod
return h, pw
hf1, pf1 = build_hash(S, BASE1, MOD1)
hf2, pf2 = build_hash(S, BASE2, MOD2)
sr1, pr1 = build_hash(S[::-1], BASE1, MOD1)
sr2, pr2 = build_hash(S[::-1], BASE2, MOD2)
def get_fwd(l, r, h, pw, mod):
return (h[r+1] - h[l] * pw[r-l+1]) % mod
def get_rev(l, r, h, pw, mod):
rl, rr = n-1-r, n-1-l
return (h[rr+1] - h[rl] * pw[rr-rl+1]) % mod
def is_pal(l, r):
if l > r or l == r: return True
if get_fwd(l, r, hf1, pf1, MOD1) != get_rev(l, r, sr1, pr1, MOD1): return False
return get_fwd(l, r, hf2, pf2, MOD2) == get_rev(l, r, sr2, pr2, MOD2)
R_odd = [0] * n
for c in range(n):
lo, hi = 0, min(c, n-1-c)
while lo < hi:
mid = (lo + hi + 1) >> 1
if is_pal(c-mid, c+mid): lo = mid
else: hi = mid - 1
R_odd[c] = lo
R_even = [0] * n
for c in range(n-1):
lo, hi = 0, min(c+1, n-1-c)
while lo < hi:
mid = (lo + hi + 1) >> 1
if is_pal(c-mid+1, c+mid): lo = mid
else: hi = mid - 1
R_even[c] = lo
out = []
for _ in range(Q):
l, r = map(int, input().split())
l -= 1; r -= 1
best = 1
for c in range(l, r+1):
rad = min(R_odd[c], c - l, r - c)
best = max(best, 2 * rad + 1)
for c in range(l, r):
rad = min(R_even[c], c - l + 1, r - c)
if rad > 0:
best = max(best, 2 * rad)
out.append(best)
print('\n'.join(map(str, out)))
solve()
Step-by-Step 解説
1ローリングハッシュの二重化
単一ハッシュは衝突の恐れがある。$2^{61}-1$（Mersenne 素数）と $2^{31}-1$ の二重ハッシュでほぼ確実に衝突回避できる。
単一ハッシュは衝突の恐れがある。$2^{61}-1$（Mersenne 素数）と $2^{31}-1$ の二重ハッシュでほぼ確実に衝突回避できる。
2回文判定 is_pal(l, r)
前向きハッシュと逆向きハッシュを比較する。$S[l..r]$ と $S_{\text{rev}}[n-1-r..n-1-l]$ のハッシュが等しければ回文。
前向きハッシュと逆向きハッシュを比較する。$S[l..r]$ と $S_{\text{rev}}[n-1-r..n-1-l]$ のハッシュが等しければ回文。
3各中心の最長回文半径の二分探索
Manacher 法（$O(N)$）が最適だが、ローリングハッシュ + 二分探索で $O(N \log N)$ も実用的。各中心 $c$ に対して
Manacher 法（$O(N)$）が最適だが、ローリングハッシュ + 二分探索で $O(N \log N)$ も実用的。各中心 $c$ に対して
is_pal(c-mid, c+mid) を二分探索する。
4奇数長・偶数長の別管理
奇数長回文: 中心が位置 $c$、半径 $R$、$S[c-R..c+R]$ が回文。偶数長回文: 中心が $c$ と $c+1$ の間、半径 $R$、$S[c-R+1..c+R]$ が回文。
奇数長回文: 中心が位置 $c$、半径 $R$、$S[c-R..c+R]$ が回文。偶数長回文: 中心が $c$ と $c+1$ の間、半径 $R$、$S[c-R+1..c+R]$ が回文。
5クエリへの回答
区間 $[l,r]$ 内の各中心 $c$ について、実際に使える回文半径は $\min(R[c], c-l, r-c)$。本解の学習用実装は $O(N)$ per query。本番は Sparse Table 応用で $O(\sqrt{N})$ や $O(\log^2 N)$ を目指す。
区間 $[l,r]$ 内の各中心 $c$ について、実際に使える回文半径は $\min(R[c], c-l, r-c)$。本解の学習用実装は $O(N)$ per query。本番は Sparse Table 応用で $O(\sqrt{N})$ や $O(\log^2 N)$ を目指す。
計算量
前処理: $O(N \log N)$（ハッシュ構築 + 全中心の二分探索）
クエリ（本実装）: $O(N)$ per query
クエリ（最適化）: $O(\sqrt{N})$ per query（平方分割）
空間: $O(N)$
クエリ（本実装）: $O(N)$ per query
クエリ（最適化）: $O(\sqrt{N})$ per query（平方分割）
空間: $O(N)$
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 逆向きハッシュのインデックス計算ミス | 反転後の位置を誤る | rl = n-1-r, rr = n-1-l |
| 偶数長回文の境界条件ミス | 中心が位置の「間」にある | S[c-rad+1..c+rad] を明示 |
| 二分探索の境界 lo < hi vs lo <= hi | 最大値を取り損なう | 答えが lo になるよう hi = mid - 1 |
| ハッシュのモジュラー演算で負の値 | Python の % は正だが計算ミス | % mod で常に正にする |
次のステップ
- 発展問題: 区間内の相異なる回文部分文字列の個数カウント（Eertree + Mo's Algorithm）
- 関連: Day036 Q5（ローリングハッシュ二分探索 最長共通部分文字列）の復習
- 応用: DNA 配列解析での回文認識（制限酵素切断部位の特定）