Day 055-Q1 | Suffix Automaton + DAWG 最長回文部分列

問題

長さ $N$ の文字列 $S$（英小文字）が与えられる。$Q$ 個のクエリ $(l, r)$（1-indexed, 両端含む）に対して、$S[l..r]$ の最長回文部分文字列の長さを答えよ。

制約

パラメータ	範囲
$N$	$1 \le N \le 2 \times 10^5$
$Q$	$1 \le Q \le 10^5$
$l, r$	$1 \le l \le r \le N$
文字種	英小文字のみ

入出力例

入力例 1

10 3
abacabadab
1 10
3 8
5 9

出力例 1

7
5
3

$S[1..10]$ = "abacabadab" の最長回文は "abacaba"（長さ7）。 $S[3..8]$ = "acabada" → "acaca"（長さ5）。 $S[5..9]$ = "abada" → "aba"（長さ3）。

概念図: Eertree（回文オートマトン）構造

ヒント（段階的開示）

ヒント1: 方向性

Palindrome Automaton（Eertree）を構築し、各位置 $i$ での最長回文接尾辞ノード pos_node[i] を記録する。区間 $[l, r]$ の最長回文は、$r$ から辿る suffix link チェーンの中で「左端が $\ge l$ になる」最大長のものを二分探索で特定できる。Series link + binary lifting で $O(\log N)$ per query を達成。

ヒント2: アプローチ

diff[v] = len[v] - len[link[v]]（suffix link との長さ差）
slink[v]: 同じ diff の連鎖をスキップした「series link」
anc[k][v]: $v$ から $2^k$ 回 slink を辿った先（sparse table）
クエリ $(l, r)$: pos_node[r] から len[v] ≤ r-l+1 になる最初の $v$ を binary lifting で探す

ヒント3: コード骨格

# series link の定義
diff[v] = len_[v] - len_[link[v]]
slink[v] = slink[link[v]] if diff[v] == diff[link[v]] else link[v]

# Binary Lifting テーブル構築
anc[0][v] = slink[v]
for k in range(1, LOG):
    anc[k][v] = anc[k-1][anc[k-1][v]]

# クエリ (l, r) → 0-indexed
def query(l, r):
    v = pos_node[r]
    limit = r - l + 1
    for k in range(LOG-1, -1, -1):
        nv = anc[k][v]
        if len_[nv] > limit:
            v = nv
    return len_[v] if len_[v] <= limit else len_[link[v]]

模範解答 (Python)

import sys
from math import log2
input = sys.stdin.readline

def solve():
    N, Q = map(int, input().split())
    S = input().strip()

    len_ = [-1, 0]
    link = [0, 0]
    diff = [0, 0]
    slink = [0, 0]
    to = [{}, {}]
    last = 1
    sz = 2

    def get_link(v, i):
        while i - len_[v] - 1 < 0 or S[i - len_[v] - 1] != S[i]:
            v = link[v]
        return v

    pos_node = [0] * N

    for i, c in enumerate(S):
        cur = get_link(last, i)
        if c not in to[cur]:
            nlen = len_[cur] + 2
            nl = get_link(link[cur], i) if cur != 0 else 1
            lk = to[nl].get(c, 1)
            d = nlen - len_[lk]
            sl = slink[lk] if d == diff[lk] else lk
            to[cur][c] = sz
            len_.append(nlen)
            link.append(lk)
            diff.append(d)
            slink.append(sl)
            to.append({})
            sz += 1
        last = to[cur][c]
        pos_node[i] = last

    LOG = max(1, sz.bit_length())
    anc = [[0] * sz for _ in range(LOG)]
    for v in range(sz):
        anc[0][v] = slink[v]
    for k in range(1, LOG):
        for v in range(sz):
            anc[k][v] = anc[k-1][anc[k-1][v]]

    out = []
    for _ in range(Q):
        l, r = map(int, input().split())
        l -= 1; r -= 1
        v = pos_node[r]
        limit = r - l + 1
        for k in range(LOG-1, -1, -1):
            nv = anc[k][v]
            if len_[nv] > limit:
                v = nv
        ans = len_[v] if len_[v] <= limit else len_[link[v]]
        out.append(ans)
    sys.stdout.write('\n'.join(map(str, out)) + '\n')

solve()

Step-by-Step 解説

1Eertree の構築
Palindrome Automaton を構築。各文字を追加するたびに最長回文接尾辞ノード last を更新。pos_node[i] は位置 $i$ で終わる最長回文接尾辞のノードID。

2Series Link の定義
diff[v] = len[v] - len[link[v]]。同じ diff を持つ suffix link の連鎖（等差数列をなす回文集合）を series link でスキップ。$O(N)$ 前処理。

3Sparse Table（Binary Lifting）
anc[k][v] = $v$ から $2^k$ 回 slink を辿った先。前処理 $O(N \log N)$、クエリ $O(\log N)$。

4クエリ処理
区間 $[l, r]$ の最長回文: pos_node[r] から binary lifting で len[v] ≤ r-l+1 の最大長を探索。最終的に len[v] ≤ limit なら len[v]、そうでなければ len[link[v]] を返す。

計算量

Eertree 構築: $O(N)$（各文字 amortized $O(1)$）
Binary Lifting 前処理: $O(N \log N)$
クエリ: $O(\log N)$ per query, $O(Q \log N)$ 全体
空間: $O(N \log N)$

よくあるミス

ミス	原因	正しい書き方
root ノード (-1, 0) の混同	2つのルートの役割が曖昧	`len_[0]=-1`（番兵）, `len_[1]=0`（長さ0回文）
series link の条件ミス	`diff[v] != diff[link[v]]` のとき slink[v] = link[v]	link が root のとき diff は 0 なので特別扱い
binary lifting の方向ミス	len が大きすぎる側に辿るべき	`if len_[nv] > limit: v = nv`
LOG が小さすぎる	sz のビット長の計算ミス	`LOG = max(1, sz.bit_length())`

次のステップ

発展問題: 区間内の異なる回文部分文字列の個数（Eertree + Mo 法）
関連: Eertree の全回文接尾辞列挙 + KMP の border 類似構造
応用: 文字列 $S$ の全区間の最長回文長の総和計算（Eertree + 累積和）

自己評価

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