Palindrome Tree (Eertree) - Cây Xâu Đối Xứng¶

Tác giả: FPTOJ Team
Nội dung tham khảo từ: CP-Algorithms - Palindrome Tree

1. Bản chất vấn đề¶

Bài toán: Đếm số palindrome con phân biệt¶

Cho xâu $S$ độ dài $N$. Đếm số xâu con palindrome phân biệt trong $S$.

Cách thường: Duyệt tất cả $O(N^2)$ xâu con, kiểm tra palindrome $O(N)$ mỗi xâu $\Rightarrow O(N^3)$.

Palindrome Tree (Eertree): Xây dựng trong $O(N)$, mỗi palindrome là 1 nút trong cây.

So sánh¶

Phương pháp	Thời gian	Không gian
Duyệt + Manacher	$O(N^2)$	$O(N)$
Hashing	$O(N^2)$	$O(N^2)$
Palindrome Tree	$O(N)$	$O(N)$

2. Tư duy cốt lõi¶

Cấu trúc cây¶

Palindrome Tree có 2 gốc:

Node $-1$: Gốc ảo (độ dài $-1$), dùng cho palindrome độ dài lẻ.
Node $0$: Gốc cho chẵn palindrome (độ dài $0$).

Mỗi nút đại diện cho 1 palindrome duy nhất. Cạnh $c$ từ node $u$ đến node $v$ nghĩa là: palindrome $v$ = $c$ + palindrome $u$ + $c$.

Mỗi nút lưu:

len: độ dài palindrome
link: suffix link (palindrome đối xứng dài nhất là hậu tố đúng của palindrome hiện tại)
next[c]: palindrome con khi thêm ký tự $c$ vào 2 đầu

Trace chi tiết¶

Xâu: $S = \text{"abacaba"}$

Bước	Ký tự	Palindrome mới tạo	Độ dài	Suffix link
0	$a$	$a$	1	→ node 0 (rỗng)
1	$b$	$b$	1	→ node 0
2	$a$	$aba$	3	→ node $a$
3	$c$	$c$	1	→ node 0
4	$a$	$aca$	3	→ node $a$
5	$b$	$bacab$	5	→ node $b$
6	$a$	$abacaba$	7	→ node $aba$

Tổng palindrome phân biệt: $\{a, b, c, aba, aca, bacab, abacaba\}$ = 7.

Suffix Link¶

Suffix link của node $u$ là palindrome đối xứng dài nhất đúng là hậu tố của palindrome $u$.

Ví dụ: suffix link của $abacaba$ → $aba$ (vì $aba$ là hậu tố đúng của $abacaba$ và là palindrome).

flowchart LR
    N1["a (len=1)"] --> R0["rỗng (len=0)"]
    N2["b (len=1)"] --> R0
    N3["aba (len=3)"] --> N1
    N4["c (len=1)"] --> R0
    N5["aca (len=3)"] --> N1
    N6["bacab (len=5)"] --> N2
    N7["abacaba (len=7)"] --> N3

3. Phân tích tính đúng đắn¶

Tại sao mỗi nút là palindrome duy nhất?¶

Khi thêm ký tự $c$ vào 2 đầu palindrome $P$, ta được palindrome $cPc$. Nếu $cPc$ chưa tồn tại trong cây, tạo nút mới.

Suffix link đảm bảo mỗi palindrome chỉ được tạo đúng 1 lần.

Tại sao suffix link tạo cây?¶

Suffix link của palindrome $P$ luôn ngắn hơn $P$ (trừ node gốc). Do đó, suffix link tạo thành cây có gốc là node $0$ (palindrome rỗng).

4. Đánh giá độ phức tạp¶

Thao tác	Thời gian	Không gian
Xây Palindrome Tree	$O(N)$	$O(N \cdot
Đếm palindrome phân biệt	$O(N)$	$O(1)$
Số palindrome kết thúc tại vị trí $i$	$O(1)$ mỗi vị trí	$O(1)$

$|\Sigma|$ = kích thước bảng chữ cái.

Code minh họa¶

C++Python

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

struct PalindromeTree {
    struct Node {
        int len, link;
        int next[26];
        Node() : len(0), link(0) { memset(next, 0, sizeof(next)); }
    };

    string s;
    vector<Node> tree;
    int last, sz;

    PalindromeTree() {
        tree.resize(2);
        tree[0].len = -1; tree[0].link = 0;  // node 0: gốc lẻ (len=-1 để "aba" mở rộng đều 2 đầu)
        tree[1].len = 0;  tree[1].link = 0;  // node 1: gốc chẵn rỗng (len=0)
        last = 1; sz = 2;  // last: palindrome hậu tố dài nhất của tiền tố đã xử lý
    }

    void extend(int pos) {
        int cur = last;  // cur: bắt đầu từ palindrome hậu tố dài nhất
        int c = s[pos] - 'a';  // c: ký tự hiện tại (dạng chỉ số)

        // Tìm palindrome P sao cho s[pos-1-|P|] == s[pos] (mở rộng được thêm 1 cặp)
        while (true) {
            int curlen = tree[cur].len;  // curlen: độ dài palindrome đang thử
            // pos-1-curlen: vị trí đối xứng bên trái; >= 0 để không tràn mảng
            if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
                break;
            cur = tree[cur].link;  // không mở rộng được → lùi về suffix link ngắn hơn
        }

        if (tree[cur].next[c]) {  // palindrome mới đã tồn tại → không tạo node
            last = tree[cur].next[c];
            return;
        }

        last = sz++;  // last mới: node palindrome vừa tạo
        tree.push_back(Node());
        tree[last].len = tree[cur].len + 2;  // thêm 1 cặp ký tự 2 đầu → dài thêm 2
        tree[cur].next[c] = last;  // gắn cạnh c từ P đến palindrome mới

        if (tree[last].len == 1) {  // palindrome 1 ký tự → link về gốc rỗng
            tree[last].link = 1;
            return;
        }

        // Tìm suffix link: palindrome đối xứng dài nhất là hậu tố đúng
        cur = tree[cur].link;
        while (true) {
            int curlen = tree[cur].len;
            if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
                break;
            cur = tree[cur].link;
        }
        tree[last].link = tree[cur].next[c];
    }

    int countDistinct() {
        return sz - 2; // trừ 2 node gốc
    }
};

int main() {
    string s;
    cin >> s;

    PalindromeTree pt;
    pt.s = s;

    for (int i = 0; i < (int)s.size(); i++) {
        pt.extend(i);
    }

    cout << pt.countDistinct() << "\n";
    return 0;
}

class PalindromeTree:
    def __init__(self):
        self.tree = [{'len': -1, 'link': 0, 'next': {}},
                     {'len': 0, 'link': 0, 'next': {}}]
        self.last = 1
        self.s = ''

    def extend(self, pos):
        c = self.s[pos]
        cur = self.last
        while True:
            curlen = self.tree[cur]['len']
            if pos - 1 - curlen >= 0 and self.s[pos - 1 - curlen] == c:
                break
            cur = self.tree[cur]['link']

        if c in self.tree[cur]['next']:
            self.last = self.tree[cur]['next'][c]
            return

        new_node = len(self.tree)
        self.tree.append({'len': self.tree[cur]['len'] + 2, 'link': 0, 'next': {}})
        self.tree[cur]['next'][c] = new_node
        self.last = new_node

        if self.tree[new_node]['len'] == 1:
            self.tree[new_node]['link'] = 1
            return

        cur = self.tree[cur]['link']
        while True:
            curlen = self.tree[cur]['len']
            if pos - 1 - curlen >= 0 and self.s[pos - 1 - curlen] == c:
                break
            cur = self.tree[cur]['link']
        self.tree[new_node]['link'] = self.tree[cur]['next'][c]

    def count_distinct(self):
        return len(self.tree) - 2

s = input().strip()
pt = PalindromeTree()
pt.s = s
for i in range(len(s)):
    pt.extend(i)
print(pt.count_distinct())

5. Lỗi thường gặp (SAI / ĐÚNG)¶

Lỗi 1: Quên 1 trong 2 node gốc

// SAI: chỉ tạo 1 gốc → palindrome lẻ đầu tiên không mở rộng được
tree.resize(1); tree[0].len = 0; tree[0].link = 0; last = 0;

// ĐÚNG: luôn 2 gốc — node 0 (len=-1) cho lẻ, node 1 (len=0) cho chẵn
tree.resize(2);
tree[0].len = -1; tree[0].link = 0;
tree[1].len = 0;  tree[1].link = 0;
last = 1; sz = 2;
// Đáp án = sz - 2 (trừ 2 gốc) — quên trừ là sai +2.

Lỗi 2: Link của palindrome độ dài 1

// SAI: cho palindrome len=1 đi tìm link bằng vòng while chung → có thể link về chính nó
// ĐÚNG: len == 1 luôn link về node 1 (rỗng), return ngay
if (tree[last].len == 1) { tree[last].link = 1; return; }

Lỗi 3: s[pos-1-curlen] tràn chỉ số âm

// SAI: bỏ kiểm tra biên → pos-1-curlen = -1 khi palindrome dài chạm đầu xâu
if (s[pos - 1 - curlen] == s[pos]) break;

// ĐÚNG: luôn kiểm tra >= 0 trước khi so ký tự
if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) break;

Bài tập luyện tập¶

Mã bài	Tên bài tập	Độ khó	Chủ đề
`str-pald`	Đếm palindrome phân biệt (Palindrome Tree)	⭐⭐⭐	Câu lệnh cơ bản của Eertree
`str-palcnt`	Tổng palindrome con (kể overlap)	⭐⭐	Đếm tất cả palindrome
`str-pal0`	Palindrome chứa ký tự đầu tiên	⭐⭐	Truy vấn vị trí
`stra-cntpal`	Đếm palindrome con (Manacher)	⭐⭐⭐	Đếm palindrome bằng Manacher
`stra-mana`	Palindrome dài nhất (Manacher)	⭐⭐⭐	Bài cơ bản Manacher
`man-cnt`	Đếm cặp palindrome	⭐⭐⭐	Manacher nâng cao
`man-even`	Palindrome độ dài chẵn	⭐⭐⭐	Manacher nâng cao
`man-dst`	Đếm palindrome phân biệt	⭐⭐⭐	Manacher + Hash
`man-pos`	Palindrome chứa vị trí cho trước	⭐⭐⭐	Manacher + vị trí

Bước	Ký tự	Palindrome mới tạo	Độ dài	Suffix link
0	\(a\)	\(a\)	1	→ node 0 (rỗng)
1	\(b\)	\(b\)	1	→ node 0
2	\(a\)	\(aba\)	3	→ node \(a\)
3	\(c\)	\(c\)	1	→ node 0
4	\(a\)	\(aca\)	3	→ node \(a\)
5	\(b\)	\(bacab\)	5	→ node \(b\)
6	\(a\)	\(abacaba\)	7	→ node \(aba\)