Palindrome Tree (Eertree)

Palindrome Tree (hay Eertree, đọc là "palindromic tree") là cấu trúc dữ liệu lưu trữ tất cả các xâu con palindrome (đối xứng) phân biệt của một xâu. Nó được xây dựng trực tuyến (online — thêm từng ký tự một) trong tổng thời gian $O(N·\log \Sigma )$ (hoặc $O(N)$ với mảng con trực tiếp), thay vì $O(N^2)$ khi liệt kê thủ công mọi xâu con rồi kiểm tra đối xứng.

Điểm mấu chốt khiến Eertree gọn nhẹ: một xâu độ dài $N$ chỉ có tối đa $N$ palindrome con phân biệt. Vì vậy cây chỉ cần $N+2$ node (gồm 2 node gốc đặc biệt), cho phép trả lời nhanh các câu hỏi như: có bao nhiêu palindrome con phân biệt?, mỗi palindrome xuất hiện bao nhiêu lần?, palindrome dài nhất kết thúc tại mỗi vị trí?.

Ý tưởng / Trực giác

Vì sao chỉ có tối đa $N$ palindrome phân biệt?

Xét xâu $s$ và thêm dần từng ký tự. Khi thêm ký tự ở vị trí $i$, ta hỏi: có palindrome mới (chưa từng xuất hiện) nào kết thúc tại $i$ không? Palindrome kết thúc tại $i$ mà dài nhất chỉ có một; mọi palindrome mới xuất hiện lần đầu phải là palindrome dài nhất kết thúc tại $i$ (vì palindrome ngắn hơn kết thúc tại $i$ đồng thời là hậu tố của palindrome dài nhất, mà hậu tố palindrome đó cũng là tiền tố của nó, nên đã từng xuất hiện sớm hơn). Suy ra mỗi vị trí $i$ sinh nhiều nhất một palindrome mới ⇒ tổng cộng tối đa $N$ palindrome phân biệt. Đây chính là lý do Eertree có kích thước tuyến tính.

Hai node gốc

Eertree quản lý palindrome chẵn và lẻ thống nhất bằng hai node "ảo":

• Root $-1$ (imaginary root): palindrome giả độ dài $-1$. Nó là cha của mọi palindrome lẻ độ dài $1$ (khi bọc 1 ký tự quanh độ dài $-1$ ta được độ dài $1$).
• Root $0$: palindrome rỗng độ dài $0$. Là cha của mọi palindrome chẵn độ dài $2$. Suffix link của nó trỏ về root $-1$.

Mỗi node lưu gì

• len[u]: độ dài palindrome mà node $u$ đại diện.
• link[u] (suffix link): trỏ tới palindrome hậu tố thực sự dài nhất của $u$ (hậu tố vừa là palindrome, khác chính $u$). Đây là "trục xương sống" giúp di chuyển nhanh.
• to[u][c]: cạnh — nếu bọc ký tự $c$ vào hai đầu palindrome $u$ thì được palindrome $c·u·c$.

Tại sao thuật toán thêm ký tự lại đúng?

Để thêm ký tự $c=s[i]$, ta cần tìm palindrome dài nhất $A$ là hậu tố hiện tại sao cho ký tự đứng ngay trước $A$ trong $s$ cũng bằng $c$. Khi đó $c·A·c$ là palindrome mới kết thúc tại $i$. Ta tìm $A$ bằng cách đi theo chuỗi suffix link từ node last (palindrome dài nhất kết thúc tại $i-1$): mỗi suffix link cho một palindrome hậu tố ngắn hơn, ta dừng ở cái đầu tiên thỏa $s[i-len-1]=s[i]$. Vì các suffix link tạo thành chuỗi giảm độ dài nghiêm ngặt, vòng lặp luôn kết thúc (cùng lắm dừng tại root $-1$, khi đó tạo palindrome độ dài $1$).

Suffix link của node mới cũng tìm tương tự: tiếp tục đi theo suffix link từ palindrome cha để tìm hậu tố palindrome dài nhất khác chính nó.

Ví dụ chạy tay

Xây Eertree cho xâu $s=$ eertree (lấy chính tên cấu trúc!). Ta đặt một sentinel @ ở đầu để biên không bao giờ khớp. Ký hiệu node: (len).

Khởi tạo hai gốc:

node 0: root(-1)   len=-1   link=0
node 1: root(0)    len= 0   link=0
last = 1

Thêm dần từng ký tự, theo dõi last = palindrome dài nhất kết thúc tại vị trí hiện tại:

 i :  1   2   3   4   5   6   7
 s : '@' e   e   r   t   r   e   e

Bước i=1, ký tự e:

• Từ last=1 đi suffix link, tìm vị trí có s[i-len-1]=s[i]. Tạo palindrome "e".
• Tạo node 2 (1), link=1 (palindrome độ dài 1 luôn trỏ root 0). last=2.

Bước i=2, ký tự e:

• Trước "e" (node 2) có ký tự e ⇒ bọc thành "ee".
• Tạo node 3 (2), link=2 (hậu tố palindrome dài nhất của "ee" là "e"). last=3.

Bước i=3, ký tự r: palindrome mới "r" ⇒ node 4 (1), link=1. last=4.

Bước i=4, ký tự t: palindrome mới "t" ⇒ node 5 (1), link=1. last=5.

Bước i=5, ký tự r:

• s = "@eertr". Ký tự trước vị trí 5: tìm hậu tố palindrome $A$ với ký tự đứng trước $A$ bằng r. Đó là "t" (node 5): trước "t" là r? Không, trước t là r... thực ra ta bọc r quanh "t" ⇒ "rtr".
• Tạo node 6 (3) cho "rtr", link=4 (hậu tố palindrome dài nhất là "r"). last=6.

Bước i=6, ký tự e: palindrome mới kết thúc tại đây dài nhất là "e" (node 2 đã có). Không tạo node mới. last=2.

Bước i=7, ký tự e: bọc e quanh "e" ⇒ "ee" (node 3 đã có). Không tạo node mới. last=3.

Cây kết quả (mũi tên --c--> là cạnh to, đường nét đứt là suffix link ..>):

            root(-1) [0]                 root(0) [1]
              |  \  \                       |
            e |  r| t|                    ee|
              v   v  v                      v
           "e"(2) "r"(4) "t"(5)          "ee"(3)
                    |
                  r | t   (cạnh r->? thực ra "rtr")
                    v
                "rtr"(6)

 suffix link:  "ee"(3) ..> "e"(2) ..> root(0)(1) ..> root(-1)(0)
               "rtr"(6) ..> "r"(4) ..> root(0)(1)

Tổng số palindrome phân biệt = số node − 2 = 7 − 2 = 5, đó là: e, ee, r, t, rtr. Đúng như đếm tay trên xâu eertree.

Cài đặt

#include <bits/stdc++.h>
using namespace std;

struct Eertree {
    static const int ALPHA = 26;
    struct Node {
        int len, link;
        int to[ALPHA];
        long long cnt;   // số lần palindrome này là "hậu tố dài nhất" khi build
    };
    vector<Node> t;
    string s;
    int last;            // node của palindrome hậu tố dài nhất hiện tại

    Eertree(int n = 0) {
        t.reserve(n + 2);
        // node 0 = root(-1), node 1 = root(0)
        t.push_back({-1, 0, {}, 0});
        t.push_back({ 0, 0, {}, 0});
        fill(t[0].to, t[0].to + ALPHA, -1);
        fill(t[1].to, t[1].to + ALPHA, -1);
        last = 1;
        s = "@";         // sentinel: không thuộc bảng chữ cái, chặn biên trái
    }

    // Tụt theo suffix link từ v đến khi ký tự ngay TRƯỚC palindrome bằng s[i]
    int getLink(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 = (int)s.size() - 1;
        int x = c - 'a';
        int cur = getLink(last, i);          // tìm palindrome A để bọc thành c.A.c

        if (t[cur].to[x] == -1) {            // palindrome c.A.c CHƯA tồn tại -> tạo node mới
            Node nw;
            nw.len  = t[cur].len + 2;
            nw.cnt  = 0;
            fill(nw.to, nw.to + ALPHA, -1);

            if (nw.len == 1)
                nw.link = 1;                 // palindrome độ dài 1 -> suffix link là root(0)
            else {
                int q = getLink(t[cur].link, i);   // tìm hậu tố palindrome dài nhất khác chính nó
                nw.link = t[q].to[x];
            }
            t[cur].to[x] = (int)t.size();
            t.push_back(nw);
        }
        last = t[cur].to[x];
        t[last].cnt++;                       // ghi nhận 1 lần xuất hiện (hậu tố dài nhất)
    }

    // Quy số lần xuất hiện THỰC SỰ: cộng dồn ngược theo suffix link.
    // Node tạo sau luôn có chỉ số lớn hơn node link của nó -> duyệt giảm dần là an toàn.
    void propagate() {
        for (int v = (int)t.size() - 1; v >= 2; --v)
            t[t[v].link].cnt += t[v].cnt;
    }

    int distinctCount() { return (int)t.size() - 2; }  // số palindrome con phân biệt
};

int main() {
    string s; 
    cin >> s;
    Eertree et(s.size());
    for (char c : s) et.add(c);
    et.propagate();

    cout << et.distinctCount() << "\n";      // số palindrome con phân biệt
    // et.t[v].len  = độ dài; et.t[v].cnt = số lần xuất hiện của palindrome v (v >= 2)
    return 0;
}

Tại mỗi bước, et.t[last].len chính là độ dài palindrome dài nhất kết thúc tại vị trí vừa thêm — đây là thứ trực tiếp giải bài "palindrome dài nhất kết thúc tại mỗi vị trí".

Độ phức tạp

Vì sao build là $O(N)$? Lập luận amortized giống suffix automaton: trong getLink, mỗi lần tụt suffix link làm giảm độ dài của last, còn mỗi add chỉ làm len[last] tăng tối đa 2. Tổng độ tăng qua $N$ bước là $O(N)$, nên tổng số lần tụt link cũng $O(N)$. Vậy build là tuyến tính (khi dùng mảng to[ALPHA] truy cập $O(1)$; nếu dùng map thì thêm hệ số $\log \Sigma$).

Bộ nhớ $O(N·\Sigma )$ do mỗi node lưu mảng to kích thước $\Sigma =26$. Với $\Sigma$ lớn (vd 256) nên thay bằng unordered_map<int,int> để tiết kiệm, đổi lấy hằng số chậm hơn.

⚠️ Lỗi thường gặp

• Quên sentinel ở đầu xâu. Hàm getLink truy cập s[i - len - 1]. Khi len = -1 (root −1), biểu thức là s[i + 1 - 1] = s[i] — luôn khớp, đúng ý đồ. Nhưng nếu không đặt s[0] = '@' và đánh chỉ số từ 0, ta sẽ truy cập s[-1] ⇒ lỗi truy cập ngoài mảng. Luôn để xâu bắt đầu bằng một ký tự không thuộc bảng chữ cái rồi thêm ký tự thật từ chỉ số 1.

• Tràn số khi đếm số lần xuất hiện. Tổng số lần xuất hiện của tất cả palindrome có thể lên tới $\Theta (N^2)$ (vd xâu toàn a: palindrome a xuất hiện $N$ lần, aa xuất hiện $N-1$ lần...). Dùng int cho cnt sẽ tràn khi $N\ge 5\times {10}^4$. Phải dùng long long.

• Quy cnt sai thứ tự. cnt lúc build chỉ đếm số lần palindrome là hậu tố dài nhất; số lần xuất hiện thực sự phải cộng dồn từ con về tổ tiên theo suffix link. Nếu cộng dồn theo thứ tự tăng chỉ số node sẽ sai. Nhờ tính chất node tạo sau luôn có chỉ số lớn hơn suffix link của nó, ta duyệt giảm dần từ node cuối về node 2 mới đúng.

• Khởi tạo link của root sai. Phải đặt link[root(0)] = root(-1) (node 1 trỏ node 0). Bỏ qua bước này khiến getLink rơi vào vòng lặp vô hạn vì không bao giờ tụt được tới root −1.

• Nhầm suffix link của palindrome độ dài 1. Palindrome độ dài $1$ (vd "a") phải có suffix link trỏ về root 0 (node 1), KHÔNG phải root −1. Nếu để trỏ root −1, các phép quy cnt và duyệt chuỗi hậu tố palindrome sẽ lệch.

• Dùng to[u][c] như cạnh "thêm 1 ký tự cuối". Khác trie/suffix automaton: cạnh trong Eertree nghĩa là bọc ký tự vào CẢ HAI đầu ($u\to c·u·c$), không phải nối thêm ký tự cuối. Hiểu nhầm điều này dẫn tới dựng cây sai hoàn toàn.

Biến thể / Mở rộng

• Đếm số palindrome con phân biệt sau mỗi lần thêm ký tự: chính là số node − 2 tại thời điểm đó (online).
• Palindrome dài nhất kết thúc tại mỗi vị trí: in len[last] sau mỗi add.
• Phân rã xâu thành ít palindrome nhất (palindromic factorization): kết hợp Eertree với series link (diff[v] = len[v] - len[link[v]] và serieslink) để DP trong $O(N\log N)$.
• So sánh với Manacher: Manacher chỉ tìm palindrome dài nhất tại mỗi tâm trong $O(N)$ nhưng không lưu trữ cấu trúc; Eertree lưu toàn bộ palindrome phân biệt nên mạnh hơn khi cần đếm/DP trên chúng.

Bài tập luyện

• Thần chú Palindrome (spellpalin) — (Sơ cấp) khởi động: kiểm tra một xâu có phải palindrome không, làm quen định nghĩa đối xứng trước khi học cấu trúc.
• Palindrome Dài Nhất (longpalin) — (Nâng cao) tìm xâu con đối xứng dài nhất; có thể giải bằng Eertree (theo dõi node có len lớn nhất) hoặc Manacher, $n\le {10}^6$.
• Tất Cả Palindrome (allpalin) — (Nâng cao) in độ dài palindrome dài nhất kết thúc tại mỗi vị trí; đây là ứng dụng kinh điển nhất của Eertree, đáp án mỗi bước là len[last].
• Ký Ức Vụn Vỡ (memory) — (Kỳ cựu) DP đường đi palindrome trên DAG; luyện tư duy palindrome nâng cao (mở rộng cách suy luận đối xứng hai đầu của Eertree sang đồ thị).