팰린드롬 트리

모든 팰린드롬 부분 문자열을 노드로 갖는 구조.

다이아몬드 II

선수 지식: 트라이

1강 모든 팰린드롬 부분 문자열의 구조: 에르트리 공식

문제

문자열 $$s$$ 안의 서로 다른 팰린드롬 부분 문자열은 최대 $$n$$ 개임이 알려져 있다(palindromic factor 한계). 팰린드롬 트리(eertree, palindromic tree)는 이 $$O(n)$$ 개의 팰린드롬을 노드로 갖고, 온라인 $$O(n)$$ 에 구성되며, 각 팰린드롬의 등장 횟수·길이 등을 일괄 계산한다.

두 개의 루트

eertree에는 특별한 가짜 루트 두 개가 있다.

길이 $$-1$$ 루트(imaginary root): suffix link 사슬의 바닥.
길이 $$0$$ 루트(empty string): 짝수 길이 팰린드롬의 시작점.

각 노드 $$v$$ 는 한 팰린드롬을 나타내며 len(v)(길이), link(v)(가장 긴 진 팰린드롬 접미사로의 링크), 글자별 전이 next(v, c) 를 가진다. 전이 next(v,c) 는 " $$v$$ 양옆에 글자 $$c$$ 를 붙인 팰린드롬 $c\,v\,c$ ".

suffix link

link(v) 는 $$v$$ 의 가장 긴 진(proper) 팰린드롬 접미사 노드를 가리킨다. 길이 $$-1$$ 루트는 모든 길이 1 팰린드롬의 link 바닥 역할을 한다. 이 link들은 트리를 이루며, 등장 횟수 집계 등 트리 DP의 골격이 된다.

온라인 구성

글자를 하나씩 끝에 붙인다. 현재까지의 가장 긴 팰린드롬 접미사를 가리키는 last 에서 시작해, suffix link 사슬을 따라 올라가며 " $s[i] \cdot (\text{후보}) \cdot s[i]$ " 가 팰린드롬이 되는 첫 후보 $$X$$ 를 찾는다(즉 $$s[i - len(X) - 1] = s[i]$$ ). 그 자리에 새 팰린드롬 전이가 없으면 새 노드를 만들고, 그 노드의 suffix link 역시 $$X$$ 의 link 사슬을 한 번 더 따라가 결정한다.

각 글자 추가에서 사슬을 따라 올라가는 총 횟수가 amortized $$O(1)$$ (last의 깊이 증가/감소 논변)이라 전체 $$O(n)$$ .

핵심 사실

항목	값
노드 수	$\le n + 2$ (두 루트 포함)
서로 다른 팰린드롬 수	노드 수 $$- 2$$
각 팰린드롬 등장 횟수	생성 시 +1, link 사슬 따라 합산
가장 긴 회문 접미사	매 단계 `last`

2강 eertree 구현과 응용 공식

표준 구현

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct Eertree {
    struct Node { int len, link, cnt; map<char,int> next; };
    vector<Node> t;
    string s;
    int last;
    Eertree() {
        t.push_back({-1, 0, 0, {}});   // 0: imaginary root (len -1)
        t.push_back({0, 0, 0, {}});    // 1: empty root (len 0), link -> 0
        t[1].link = 0;
        last = 1;
    }
    // s[i] 양옆에 붙여 팰린드롬이 되는 후보(노드) 찾기
    int getLink(int v, int i) {
        while (i - t[v].len - 1 < 0 || s[i - t[v].len - 1] != s[i])
            v = t[v].link;
        return v;
    }
    void add(char c) {
        s += c;
        int i = s.size() - 1;
        int cur = getLink(last, i);
        if (!t[cur].next.count(c)) {            // 새 팰린드롬 발견
            int now = t.size();
            t.push_back({t[cur].len + 2, 0, 0, {}});
            if (t[now].len == 1) t[now].link = 1;     // 길이 1은 empty root로
            else t[now].link = t[getLink(t[cur].link, i)].next[c];
            t[cur].next[c] = now;
        }
        last = t[cur].next[c];
        t[last].cnt++;                          // 끝나는 팰린드롬 1회 등장
    }
    long long countOccurrences() {              // link 사슬로 등장 횟수 누적
        long long total = 0;
        for (int v = t.size() - 1; v >= 2; v--) {
            t[t[v].link].cnt += t[v].cnt;       // 자식 → 부모 합산
            total += t[v].cnt;
        }
        return total;
    }
};

자주 하는 실수

두 루트 설정. 0번은 길이 $$-1$$ , 1번은 길이 0, link(1)=0. 이 초기화가 틀리면 getLink가 무한루프.
길이 1 link. 길이 1 팰린드롬의 link는 empty root(1번).
cnt 누적 순서. 노드는 생성 순으로 link가 더 짧으므로, 인덱스 큰 것부터 작은 것으로 cnt 를 부모에 더해야 한다.
map 전이 속도. 알파벳이 작으면 고정 배열로 바꿔 가속.

응용

문제	방법
서로 다른 팰린드롬 수	노드 수 $$-2$$
각 팰린드롬 등장 횟수	cnt를 link 사슬로 합산
가장 자주 나오는 회문	(등장수 × 길이) 최대
회문 분할 수 DP	series link로 가속

series link 최적화

팰린드롬 분할(예: 문자열을 최소 팰린드롬으로 쪼개기) DP는 보통 link 사슬 길이만큼 비싸지만, series link(등차적으로 길이가 줄어드는 그룹의 대표 링크)를 추가하면 한 글자당 $O(\log n)$ 으로 가속된다. eertree는 이 회문 DP 문제군의 표준 도구다.

문제	방법
서로 다른 팰린드롬 수	노드 수 $\(-2\)$
각 팰린드롬 등장 횟수	cnt를 link 사슬로 합산
가장 자주 나오는 회문	(등장수 × 길이) 최대
회문 분할 수 DP	series link로 가속