Day 036-Q1 | Palindrome Tree（Eertree）応用：最長回文辞書順最小分割

問題

文字列 $S$（長さ $N$，英小文字）が与えられる。 $S$ を 1つ以上の回文部分文字列 に分割する方法のうち，分割数が最小のものを求めよ。さらに，最小分割数を達成する方法が複数ある場合，辞書順最小の分割を出力せよ。

制約

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

$S$ は英小文字のみ

時間制限: 2sec

メモリ: 256MB

入出力例

入力例 1

7
aabaacc

出力例 1

3
aabaa c c

入力例 2

7
abacaba

出力例 2

1
abacaba

概念図: Palindrome Tree (Eertree) 構造

Eertree は文字列の全ての相異なる回文部分文字列を管理するトライ木。根2つ（仮根・空根）からなる。

ヒント (段階的開示)

ヒント1: 方向性

Palindrome Tree（Eertree）を用いると，$S$ の各 suffix が何個の回文接尾辞を持つかを $O(N)$ で列挙できる。これを DP と組み合わせよ。

ヒント2: アプローチ

dp[i] = $S[0..i-1]$ を回文で分割するときの最小回文数。Eertree の suffix link / series link を使い，$O(N \log N)$ で全位置の DP を計算する。

ヒント3: series link の役割

series_link[v] = 同じ差（diff = len[v] - len[suf[v]]）を持つシリーズの先頭の直前ノード。
1文字ごとに series link を辿るループは $O(\log N)$ 回で終わる（各文字に対してシリーズ数は $O(\log N)$）。

v = last
while v > 1:
    pos = i + 1 - len[ser[v]] - diff[v]
    dp_ser[v] = dp[pos]
    dp[i+1] = min(dp[i+1], dp_ser[v] + 1)
    v = ser[v]

模範解答 (Python)

import sys
input = sys.stdin.readline

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

    # Palindrome Tree (Eertree)
    node_len  = [-1, 0]
    node_suf  = [0,  0]
    node_diff = [0,  0]
    node_ser  = [0,  0]
    node_dpser= [0,  0]
    node_next = [{}, {}]
    last = 1

    def get_suf(i, cur):
        while True:
            j = i - node_len[cur] - 1
            if j >= 0 and S[j] == S[i]:
                return cur
            cur = node_suf[cur]

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

    for i in range(N):
        cur = get_suf(i, last)
        c = S[i]
        if c not in node_next[cur]:
            sf = node_suf[cur]
            if cur != 0:
                sf = get_suf(i, node_suf[cur])
            nl = node_len[cur] + 2
            sf_c = node_next[sf].get(c, 1) if sf != 0 else 1
            node_len.append(nl)
            node_suf.append(sf_c)
            node_diff.append(0)
            node_ser.append(0)
            node_dpser.append(0)
            node_next.append({})
            v = len(node_len) - 1
            if nl == 1:
                node_suf[v] = 1
            node_next[cur][c] = v
            node_diff[v] = node_len[v] - node_len[node_suf[v]]
            if node_diff[v] == node_diff[node_suf[v]]:
                node_ser[v] = node_ser[node_suf[v]]
            else:
                node_ser[v] = node_suf[v]
        last = node_next[cur][c]
        v = last
        while v > 1:
            ser_v = node_ser[v]
            pos = i + 1 - node_len[ser_v] - node_diff[v]
            if 0 <= pos <= N:
                node_dpser[v] = dp[pos]
            cand = node_dpser[v] + 1
            if cand < dp[i + 1]:
                dp[i + 1] = cand
                seg_len = node_len[ser_v] + node_diff[v]
                par[i + 1] = (i + 1 - seg_len, i + 1)
            v = node_ser[v]

    print(dp[N])
    parts = []
    idx = N
    while idx > 0:
        st, en = par[idx]
        parts.append(S[st:en])
        idx = st
    parts.reverse()
    print(' '.join(parts))

solve()

Step-by-Step 解説

1Eertree 構築
文字列の全ての相異なる回文部分文字列を $O(N)$ で管理。根は2つ（仮根 len=-1，空根 len=0）。各文字を追加するたびに suffix link を辿り，新しい回文ノードを追加または既存ノードを使用。

2Series Link の計算
diff[v] = len[v] - len[suf[v]]。 series_link[v] = suf[v] if diff[v] != diff[suf[v]]， else series_link[suf[v]]。同一 diff のシリーズをまとめてスキップ。

3DP 遷移
位置 $i$ の後で終わる各回文に対し series link を辿りながら dp[i+1] を更新。 1文字あたり $O(\log N)$ 回のループで終わる。全体 $O(N \log N)$。

4経路復元
par[i] に分割点を記録し後ろから辿る。辞書順最小化は「最長回文優先」に対応。

計算量

構築: $O(N)$ 時間・空間
DP: $O(N \log N)$（series link によるシリーズ数 $= O(\log N)$）
合計: $O(N \log N)$

よくあるミス

ミス	原因	正しい書き方
suf_link の設定ミス	長さ1の回文の suf_link を仮根にすべき	`if nl==1: node_suf[v]=1`
series_link のループ条件	仮根/空根に入ると無限ループ	`while v > 1:` で終了
dp_ser のインデックス計算	pos が負になりうる	`if 0 <= pos <= N:` でガード
辞書順復元の実装	後ろから貪欲で辞書順最小にならないケース	前方から「最長回文優先」で再試行

次のステップ

発展: 回文分割数の最小化 + 各部分の長さの和の最大化（重みつき最適化）
応用: Eertree による回文部分文字列の個数カウント（distinct palindromes）

自己評価

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

Day 036-Q1 — Palindrome Tree（Eertree）応用：最長回文辞書順最小分割

問題

制約