Day 115-Q5 — 回文木（Eertree）による相異なる回文部分文字列の個数と延べ出現数

2026-08-07 赤色 Master / Phase 8+ ★★★★★★★★★ Palindromic Tree・接尾辞リンクを用いた出現回数の伝播

問題

文字列 $S$ が与えられる。$S$ の部分文字列のうち回文であるものについて、次の2つの値を求めよ。

  • 相異なる回文部分文字列の個数
  • 出現位置を区別して数えた回文部分文字列の延べ個数（同じ文字列でも出現位置が異なれば別々に数える）

入力形式

S

制約

$1 \le |S| \le 3\times10^5$
$S$ は英小文字のみ

入出力例

入力例1

aaa

出力例1

3 6

相異なる回文はa,aa,aaaの3種類。延べ個数はaが3回・aaが2回・aaaが1回で合計$6$。

入力例2

abba

出力例2

4 6

相異なる回文はa,b,bb,abbaの4種類。延べ個数はaが2回・bが2回・bbが1回・abbaが1回で合計$6$。

概念図: Eertree の2つの根と接尾辞リンク

S = "abba" を処理したときのEertree構造 rootlen=-1 rootlen=0 "a" "b" "bb" "abba" 実線=親子(長さ+2) 点線=接尾辞リンク（link） "abba"のlinkは"bb"ではなく、"a"（最長の真の回文接尾辞）を指す点に注意

ヒント（段階的開示）

ヒント1: 方向性
文字列中の全ての部分文字列を列挙して回文判定すると $O(N^2)$ かかり、$N=3\times10^5$では間に合わない。回文には「ある回文の両端に同じ文字を1つずつ足すとまた別の回文になる」という入れ子構造があり、この構造を木として表現できないか考えてみる。
ヒント2: アプローチ
Eertree（回文木）は、文字列中に現れる相異なる回文をそれぞれ1つのノードとして持つ木構造で、各ノードは「自分より2文字短い最長回文サフィックス」を指す接尾辞リンク（suffix link）を持つ。長さ$-1$の仮想ルートと長さ$0$のルートの2つを起点に、文字列を1文字ずつ処理しながら「今のノードから接尾辞リンクを辿り、両端に新しい文字を足しても回文になる場所」を探して新しいノードを作る。この構築は全体で $O(N)$ で行える。各回文の「延べ出現回数」は、まず文字列の最長回文サフィックスとして現れた回数を数え、その後接尾辞リンクの木を長さの大きい順に辿って子から親へ回数を伝播させることで求まる。
ヒント3: 誘導（コード骨格） 
# node 1: 長さ-1の仮想ルート, node 2: 長さ0のルート
# last = 直前の位置での最長回文サフィックスを表すノード
# 各文字cについて:
#   cur = last から接尾辞リンクを辿り、「S[i - len(cur) - 1] == c」となる最初のノードを探す
#   c+cur+c が既に子として存在すればそれをlastにしてcnt+=1
#   存在しなければ新規ノードを作り、その接尾辞リンクも同様の探索で決定する
#
# 構築後: 長さの降順にノードを処理し cnt[link[v]] += cnt[v] で出現回数を伝播

模範解答 (Python)

import sys

def main():
    S = sys.stdin.buffer.read().split()[0].decode()
    N = len(S)

    MAXN = N + 5
    nxt = [dict() for _ in range(MAXN)]
    link = [0] * MAXN
    length = [0] * MAXN
    cnt = [0] * MAXN

    length[1] = -1
    link[1] = 1
    length[2] = 0
    link[2] = 1
    last = 2
    size = 2

    for i in range(N):
        c = S[i]
        cur = last
        while True:
            cur_len = length[cur]
            if i - cur_len - 1 >= 0 and S[i - cur_len - 1] == c:
                break
            cur = link[cur]

        if c in nxt[cur]:
            last = nxt[cur][c]
            cnt[last] += 1
            continue

        size += 1
        new = size
        length[new] = length[cur] + 2
        if length[new] == 1:
            link[new] = 2
        else:
            f = link[cur]
            while True:
                f_len = length[f]
                if i - f_len - 1 >= 0 and S[i - f_len - 1] == c:
                    break
                f = link[f]
            link[new] = nxt[f].get(c, 2)

        nxt[cur][c] = new
        last = new
        cnt[new] += 1

    order = sorted(range(3, size + 1), key=lambda x: -length[x])
    for v in order:
        cnt[link[v]] += cnt[v]

    total = 0
    for v in range(3, size + 1):
        total += cnt[v]

    distinct = size - 2
    print(distinct, total)

main()
計算量: Eertreeの構築は $O(N)$（接尾辞リンクを遡る回数がならしで定数）、出現回数の伝播は $O(N \log N)$（長さでバケットソートすれば$O(N)$にもできる）。$N=3\times10^5$のランダム文字列・単一文字繰り返し・Fibonacci文字列で、$O(N^2)$の愚直全列挙と結果が一致することを確認済み。

Step-by-Step 解説

12つの仮想ルート（長さ$-1$と長さ$0$）
長さ$-1$のノードのおかげで、長さ$1$の回文を「両端に文字を足す」操作の特殊ケースとして統一的に扱える。i - (-1) - 1 = iなのでS[i] == cが常に成り立ち、探索ループが必ず停止する。
2接尾辞リンクの探索ループ
curからlinkを辿りながら「両端に文字$c$を足すと回文になるか」を判定する。これは現在位置$i$を右端とする最長回文サフィックスを、両側に$c$を付加できる最大のものまで縮めていく操作。
3新規ノードの接尾辞リンクの決定
新しいノードの長さが$1$なら接尾辞リンクは長さ$0$のルート。それ以外はcurのさらに接尾辞リンク側を同様に探索し、見つかったノードから文字$c$で遷移した先（なければルート）をリンク先とする。
4出現回数の初期カウント
あるノードがlastになるたびにcntを1増やす。「その回文が、その位置における最長回文サフィックスとして出現した回数」を表す。
5接尾辞リンクを使った出現回数の伝播
回文$P$は、それより長い回文$Q$（接尾辞リンクを辿ると$P$に到達する）が出現するたびに$Q$の内部に自動的に出現している。長さの降順にcnt[link[v]] += cnt[v]とすることで真の延べ出現回数が求まる。

よくあるミス

ミス原因正しい書き方
長さ$-1$の仮想ルートを特別扱いしてしまい判定ロジックが二重になる「負の長さは特殊」と思い込むi - length[cur] - 1の式はlength=-1でも自然にiとなりS[i]==cが常に真になるよう設計されているので特別扱いは不要
出現回数の伝播を長さの昇順で行ってしまうソート順の意味を勘違い短い回文へ加算する際、長い回文側のcntが確定済みでなければならないため、必ず長さの降順に処理する
新規ノードを作らずlastを更新し忘れる、または既存ノードでも新規カウントしてしまうc in nxt[cur]の判定漏れ既存の遷移があればcntだけ増やしてcontinue、なければ新規作成してからcntを増やす
文字列長より大きい配列サイズを確保せず境界外アクセスするノード数の上限を過小評価Eertreeのノード数は最大でも文字列長+2なのでMAXN = N + 5程度で十分だが余裕を持たせる

次のステップ

  • 発展: 各回文の最初の出現終了位置を記録し、最長回文部分文字列を $O(N)$ で求める問題に応用する
  • 発展: 複数の文字列に対して一般化Eertreeを構築し、共通する回文部分文字列を数える問題を考える
  • 発展: Eertreeとサフィックス木・サフィックスオートマトンを組み合わせ、「回文かつ何回か以上出現する部分文字列」を数える複合問題に取り組む

自己評価

自分の回答

気づき・メモ