Palindrome Tree (Eertree)

Wiki › Thuật toán › Thuật toán xâu

huunguyen · Last updated 8, Tháng 4, 2026, 15:18

Palindrome Tree (hay Eertree) là cấu trúc dữ liệu lưu trữ tất cả chuỗi con palindrome phân biệt của một xâu, được xây dựng trực tuyến (online) trong $O (N)$ .

Tính chất quan trọng: Một xâu độ dài $N$ có tối đa $N$ chuỗi con palindrome phân biệt (không tính trùng lặp). Palindrome Tree lưu đúng $N + 2$ node (2 node gốc đặc biệt + tối đa $N$ palindrome).

Ứng dụng:

Đếm số palindrome con phân biệt.
Đếm số lần xuất hiện của mỗi palindrome con.
Tìm palindrome con dài nhất kết thúc tại mỗi vị trí.
Phân rã xâu thành palindrome (eertree DP).

Cấu trúc

Palindrome Tree có hai node gốc đặc biệt:

Root -1: palindrome giả độ dài $- 1$ (gốc cho palindrome lẻ).
Root 0: palindrome rỗng độ dài $0$ (gốc cho palindrome chẵn). Suffix link của nó trỏ về root $- 1$ .

Mỗi node $u$ lưu:

len[u]: độ dài palindrome.
link[u]: suffix link — palindrome suffix dài nhất thực sự (khác chính nó).
to[u][c]: cạnh — palindrome mới khi thêm ký tự $c$ vào hai đầu.

Cài đặt

struct PalindromTree {
    static const int ALPHA = 26;

    struct Node {
        int len, link;
        int to[ALPHA];
        long long cnt;   // số lần xuất hiện
    };

    vector<Node> t;
    string s;
    int last;   // node tương ứng palindrome suffix dài nhất hiện tại

    PalindromTree() {
        t.push_back({-1, 0, {}, 0});  // node 0: root -1
        t.push_back({ 0, 0, {}, 0});  // node 1: root 0
        fill(t[0].to, t[0].to + ALPHA, -1);
        fill(t[1].to, t[1].to + ALPHA, -1);
        t[1].link = 0;
        last = 1;
        s = "@";   // sentinel (không thuộc alphabet)
    }

    // Tìm suffix link phù hợp để thêm ký tự c tại vị trí i
    int get_link(int v, int i) {
        while (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 = get_link(last, i);
        int x = c - 'a';

        if (t[cur].to[x] == -1) {
            // Tạo node mới
            Node nw;
            nw.len = t[cur].len + 2;
            nw.cnt = 0;
            fill(nw.to, nw.to + ALPHA, -1);

            // Suffix link của node mới
            if (nw.len == 1) {
                nw.link = 1;   // palindrome độ dài 1 → suffix link là root 0
            } else {
                int tmp = get_link(t[cur].link, i);
                nw.link = t[tmp].to[x];
            }

            t[cur].to[x] = t.size();
            t.push_back(nw);
        }

        last = t[cur].to[x];
        t[last].cnt++;
    }

    // Tính số lần xuất hiện thực sự (truyền ngược suffix link)
    void count() {
        for (int i = t.size() - 1; i >= 2; i--)
            t[t[i].link].cnt += t[i].cnt;
    }
};

Ví dụ sử dụng

int main() {
    string s; cin >> s;
    PalindromTree pt;
    for (char c : s) pt.add(c);
    pt.count();

    // Số palindrome con phân biệt
    cout << pt.t.size() - 2 << "\n";

    // Liệt kê tất cả palindrome con phân biệt với số lần xuất hiện
    for (int i = 2; i < (int)pt.t.size(); i++) {
        // pt.t[i].len = độ dài palindrome
        // pt.t[i].cnt = số lần xuất hiện
    }
}

Ví dụ: Phân rã xâu thành ít palindrome nhất

// dp[i] = số palindrome ít nhất để phân rã s[0..i-1]
// series_link[v]: suffix link "series" để nhảy nhanh trong chuỗi palindrome cùng diff
PalindromTree pt;
vector<int> dp(s.size() + 1, INT_MAX);
dp[0] = 0;

for (int i = 0; i < (int)s.size(); i++) {
    pt.add(s[i]);
    for (int v = pt.last; v > 1; v = pt.t[pt.t[v].link].to[...]) {
        if (dp[i + 1 - pt.t[v].len] != INT_MAX)
            dp[i + 1] = min(dp[i + 1], dp[i + 1 - pt.t[v].len] + 1);
    }
}

Độ phức tạp

	Độ phức tạp
Xây dựng	$O (N \cdot Σ)$ bộ nhớ, $O (N)$ thời gian
Số node	$\leq N + 2$
Đếm số lần xuất hiện	$O (N)$ sau khi build

Khi nào dùng Palindrome Tree?

Cần thông tin về tất cả palindrome con của xâu.
Bài DP liên quan đến palindrome con (phân rã, đếm).
Thay thế Manacher khi cần lưu trữ, không chỉ tìm palindrome dài nhất.

Bình luận

Không có bình luận tại thời điểm này.