Day 042-Q1 | Palindrome Partitioning DP + Eertree（最小回文分割数）

問題

文字列 $S$（長さ $N$）を回文文字列のみからなる部分文字列に分割するとき、分割数の最小値を求めよ。

制約

$1 \le N \le 3 \times 10^5$

$S$ は英小文字

時間制限: 2sec / メモリ: 256MB

入出力例

入力例 1

7
aabcdcb

出力例 1

分割例: aa + bcdcb（両方回文）→ 2分割

概念図: Eertree と Series Link

ヒント（段階的開示）

ヒント1: 方向性

$dp[i] = S[0..i)$ の最小分割数。ナイーブに $O(N^2)$ だと TLE。Eertree（回文オートマトン）で各位置の suffix palindrome を $O(N)$ で管理し、Series Link で DP 遷移を $O(N \log N)$ に短縮する。

ヒント2: アプローチ

Eertree で文字を順次追加。各ノードが固有の回文を表す。
diff[v] = len[v] - len[link[v]]（suffix link 先との長さ差）
diff が同じなら series_link[v] = series_link[link[v]]（系列の先頭へショートカット）
各位置 $i$ で DP: series を辿り $O(\log N)$ ステップで更新

ヒント3: 実装骨格

# Series: 長さが等差数列をなす suffix palindrome の列
# diff[v] = len[v] - len[link[v]]
# もし diff[v] == diff[link[v]]:
#     series_link[v] = series_link[link[v]]
# それ以外:
#     series_link[v] = link[v]

# DP 更新 (位置 i):
j = last_node
while j > 1:  # j > even_root
    k = series_link[j]  # シリーズ先頭の次のノード
    # dp[i+1] = min(dp[i+1], dp_series[j] + 1)
    j = series_link[j]
    if j <= 1: break

模範解答 (Python)

import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    S = input().strip()
    INF = float('inf')

    # Eertree (Palindrome Automaton)
    class Node:
        __slots__ = ['to', 'link', 'length', 'diff', 'slink', 'dp']
        def __init__(self, link, length):
            self.to = {}
            self.link = link
            self.length = length
            self.diff = 0
            self.slink = None
            self.dp = INF

    # 2つの根: odd(-1) と even(0)
    odd_root = Node(0, -1)
    even_root = Node(0, 0)
    nodes = [odd_root, even_root]
    # odd_root.link = odd_root (index 0)
    # even_root.link = odd_root (index 0)

    last = 1  # even_root のインデックス

    dp = [INF] * (N + 1)
    dp[0] = 0

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

    for i in range(N):
        c = S[i]
        cur = get_link(last, i)
        if c not in nodes[cur].to:
            new_len = nodes[cur].length + 2
            # suffix link を計算
            if new_len == 1:
                lnk = 1  # even_root
            else:
                lnk = nodes[get_link(nodes[cur].link, i)].to.get(c, 1)
            new_node = Node(lnk, new_len)
            new_node.diff = new_len - nodes[lnk].length
            lnk_diff = nodes[lnk].diff if lnk > 1 else 0
            if new_node.diff == lnk_diff:
                new_node.slink = nodes[lnk].slink
            else:
                new_node.slink = lnk
            nodes[cur].to[c] = len(nodes)
            nodes.append(new_node)

        last = nodes[cur].to[c]

        # Series DP
        j = last
        while j > 1:
            # k = series_link[j] (シリーズ先頭の次)
            k = nodes[j].slink if nodes[j].slink is not None else nodes[j].link
            # series の先頭ノードの dp を更新
            sl_len = nodes[k].length if k > 1 else 0
            idx = i + 1 - (nodes[j].length - sl_len)
            if 0 <= idx <= N and dp[idx] < INF:
                nodes[j].dp = min(nodes[j].dp, dp[idx])
            if nodes[j].dp < INF:
                dp[i + 1] = min(dp[i + 1], nodes[j].dp + 1)
            j = k
            if j <= 1:
                break

    print(dp[N] if dp[N] < INF else -1)

solve()

Step-by-Step 解説

1Eertree の基本構造
各ノードが固有の回文部分文字列を表す。odd root（長さ -1）と even root（長さ 0）の 2 つの根を持ち、suffix link で「現在の suffix palindrome の中で最長の proper suffix palindrome」へリンク。

2diff と series の定義
diff[v] = len[v] − len[link[v]]。diff が連続して等しいノードが「series（等差数列族）」を形成。Series link はその系列の先頭の suffix link へのショートカット。

3DP の遷移
位置 $i$ での last ノードから series link を辿ると、高々 $O(\log N)$ 個の series ヘッドに達する。各 series ヘッドで区間の dp 値を使い dp[i+1] を更新。

4計算量の導出
Eertree 構築 $O(N)$（suffix link 辿りの amortized 解析）、DP 更新 $O(\log N)$ per 文字、合計 $O(N \log N)$。

計算量

Eertree 構築: $O(N)$
Series Link 辿り（DP 更新）: $O(\log N)$ / 文字
合計: $O(N \log N)$
空間: $O(N \cdot |\Sigma|)$（最悪; hash map なら $O(N)$）

よくあるミス

ミス	原因	正しい書き方
odd root の length を 0 にする	-1 でないと単一文字が追加できない	`odd_root.length = -1`
series link を suffix link と混同	別概念	diff が等しいかどうかで判断
dp[0] = 0 を忘れる	空列のコスト	必ず初期化
last の更新順序の誤り	古い状態で DP が走る	文字追加後すぐ last を更新

次のステップ

発展問題: 各回文出現回数カウント（Eertree + suffix link DP で $O(N)$）
類題: CF 906E "Mirror Box"、LOJ #6230
応用: 最長回文分割（分割数最小化の双対）

自己評価

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