一、为什么学回文树？
Mermaid · 渲染中（下方为源码）
graph TD A[字符串] --> B[在线建回文树] B --> C[本质不同回文子串] C --> D[计数/枚举]
回文树（又称 Eertree）是用 O(n) 时间和 O(n) 空间，在线维护字符串所有本质不同回文子串的数据结构。相比 Manacher（只求半径），回文树能：
- 统计每个回文子串的出现次数
- 枚举所有本质不同回文子串
- 支持在线追加字符（动态串）
二、结构
每个节点代表一个回文子串，两条特殊边：
- next[c]：在当前回文两侧各加字符 c 得到的新回文
- fail（后缀失配链）：当前回文的最长回文真后缀
两个根节点：
- 根 0：代表长度为 −1 的"虚回文"（方便奇长度处理）
- 根 1：代表长度为 0 的空串
三、在线构造
class Node { int len, fail; int[] next = new int[26]; int cnt; }
Node[] nodes = new Node[2 * N];
nodes[0] = new Node(); nodes[0].len = -1; // 奇根
nodes[1] = new Node(); // 偶根
int last, sz = 2;
int getFail(int x, String s, int i) {
while (i - nodes[x].len - 1 < 0 || s.charAt(i - nodes[x].len - 1) != s.charAt(i))
x = nodes[x].fail;
return x;
}
void add(char c, int i, String s) {
int x = getFail(last, s, i);
int idx = c - 'a';
if (nodes[x].next[idx] != 0) { last = nodes[x].next[idx]; nodes[last].cnt++; return; }
int cur = sz++; nodes[cur] = new Node();
nodes[cur].len = nodes[x].len + 2;
nodes[x].next[idx] = cur;
if (nodes[cur].len == 1) nodes[cur].fail = 1;
else nodes[cur].fail = nodes[getFail(nodes[x].fail, s, i)].next[idx];
last = cur; nodes[cur].cnt = 1;
}