Day 018-Q2 — 回文オートマトン（Eertree）

2026-05-01 赤色 Master / Phase 8+ ★★★★★★★★★ Palindrome Automaton

問題

文字列 S（英小文字）が与えられる。以下のQ個のクエリに答えよ。

  • A i j: S[i..j] の異なる回文部分文字列の数
  • B i j: S[i..j] の最長回文部分文字列の長さ
  • C i j: S[i..j] の各回文部分文字列の出現回数の総和

制約

$|S| \le 2 \times 10^5$
$Q \le 10^5$
$0 \le l \le r < |S|$

入出力例

入力例 1

aabaa
5
A 0 4
B 0 4
C 0 4
A 0 2
B 1 3

出力例 1

4
5
8
3
3

ヒント (段階的開示)

ヒント1: 方向性
Eertree（回文オートマトン）は文字列の全回文部分文字列を O(N) で管理するデータ構造。各ノードが一つの異なる回文部分文字列に対応。
ヒント2: アプローチ
2つの根（長さ-1の奇数根と長さ0の偶数根）を持ち、各ノードはlen, link（suffix link）, edgesを持つ。左から走査しながら木を拡張。
ヒント3: 誘導 
def get_link(v, i):
    while i - lens[v] - 1 < 0 or s[i - lens[v] - 1] != s[i]:
        v = links[v]
    return v

模範解答 (Python)

import sys
from collections import defaultdict
input = sys.stdin.readline

class Eertree:
    def __init__(self):
        self.lens = [-1, 0]
        self.links = [0, 0]
        self.edges = [defaultdict(int), defaultdict(int)]
        self.cnt = [0, 0]
        self.last = 1
        self.s = []
        self.node_count = 2

    def _get_link(self, v, i):
        while i - self.lens[v] - 1 < 0 or self.s[i - self.lens[v] - 1] != self.s[i]:
            v = self.links[v]
        return v

    def add(self, c):
        self.s.append(c)
        i = len(self.s) - 1
        cur = self._get_link(self.last, i)
        if c not in self.edges[cur]:
            new_len = self.lens[cur] + 2
            if new_len == 1:
                new_link = 1
            else:
                prev = self._get_link(self.links[cur], i)
                new_link = self.edges[prev].get(c, 1)
            self.lens.append(new_len)
            self.links.append(new_link)
            self.edges.append(defaultdict(int))
            self.cnt.append(0)
            self.edges[cur][c] = self.node_count
            self.node_count += 1
        self.last = self.edges[cur][c]
        self.cnt[self.last] += 1

    def propagate(self):
        for i in range(self.node_count-1, 1, -1):
            self.cnt[self.links[i]] += self.cnt[i]

def main():
    S = input().strip()
    Q = int(input())
    for _ in range(Q):
        line = input().split()
        t, l, r = line[0], int(line[1]), int(line[2])
        sub = S[l:r+1]
        et2 = Eertree()
        for c in sub:
            et2.add(c)
        et2.propagate()
        if t == 'A':
            print(et2.node_count - 2)
        elif t == 'B':
            max_len = max(et2.lens[i] for i in range(2, et2.node_count)) if et2.node_count > 2 else 0
            print(max_len)
        else:
            total = sum(et2.cnt[i] for i in range(2, et2.node_count))
            print(total)

main()

Step-by-Step 解説

1Eertreeの構造
nodes[0]: 長さ-1の根（奇数長回文の親）、nodes[1]: 長さ0の根（偶数長回文の親）。各ノードに回文部分文字列とsuffix link。
2文字の追加
各文字追加時、現在位置 i での最長回文接尾辞を suffix link を辿って探す。見つかった回文の左に今の文字を追加した回文が新しい接尾辞。
3カウントの伝播
suffix link の逆順に cnt を伝播することで各回文ノードの総出現回数が計算可能。
4クエリへの応用
異なる回文部分文字列数 = ノード数 - 2、出現回数総和 = propagate後のcnt合計。

よくあるミス

ミス原因正しい書き方
根の初期化ミスodd.link=0が必須odd.link = 0（自己参照で無限ループ防止）
get_link の境界i - len - 1 < 0 のチェック忘れwhile条件の最初にチェック
cnt伝播の順序suffix linkは必ず短い方へnode_count-1から降順に伝播

次のステップ

  • 発展: Eertreeを使った「回文の回文」カウント
  • 応用: Online Palindrome Queries

自己評価

自分の回答

気づき・メモ