C++回文树详解（从零实现高效回文子串统计）

什么是回文树？

回文树是一种有限状态自动机，每个节点代表一个本质不同的回文子串。它有两个根节点：

• 根0：长度为 -1 的虚拟节点（用于奇数长度回文的转移）
• 根1：长度为 0 的空串节点（用于偶数长度回文的转移）

每个节点包含以下信息：

• len：该回文串的长度
• fail：后缀链接（类似AC自动机中的fail指针），指向当前回文串的最长真回文后缀
• next[26]：字符转移数组（假设只处理小写字母）
• cnt：该回文串在原串中出现的次数（可选）

回文树的构建原理

我们逐个向回文树中添加字符。设当前处理到第 i 个字符 s[i]，并维护一个变量 last 表示以 s[i-1] 结尾的最长回文后缀对应的节点。

构建步骤如下：

1. 从 last 开始，沿着 fail 指针向上跳，直到找到一个节点，其前一个字符等于 s[i]；
2. 如果该节点通过 s[i] 转移存在，则更新 last 为该子节点；
3. 否则，新建一个节点，长度为 当前节点.len + 2，并设置其 fail 指针（继续沿 fail 链找最长回文后缀）；
4. 更新 last 为新节点，并累加计数。

C++ 回文树完整实现

下面是一个完整的、注释清晰的 C++ 回文树实现，适用于处理小写英文字母组成的字符串：

#include <iostream>#include <cstring>#include <vector>using namespace std;const int MAXN = 300010; // 最大字符串长度const int ALPHA = 26;    // 字符集大小（a-z）struct PalindromicTree {    struct Node {        int len;           // 回文串长度        int fail;          // 后缀链接        int cnt;           // 出现次数（可选）        int next[ALPHA];   // 转移边        Node() {            len = cnt = fail = 0;            memset(next, 0, sizeof(next));        }    };    vector<Node> tree;    string s;    int last;      // 当前最长回文后缀节点    int n;         // 已插入字符数    int total;     // 节点总数（不包括两个根）    PalindromicTree() {        tree.clear();        tree.push_back(Node()); // 根0：len = -1        tree[0].len = -1;        tree[0].fail = 0;       // 根0的fail指向自己        tree.push_back(Node()); // 根1：len = 0        tree[1].len = 0;        tree[1].fail = 0;       // 根1的fail指向根0        last = 1;        n = 0;        total = 1;              // 当前只有根1是有效回文节点        s = "";    }    // 扩展字符串，加入字符 c    void extend(char c) {        s += c;        n++;        int cur = last;        int idx = c - 'a';        // 找到满足 s[n - 1 - node.len] == c 的节点        while (true) {            int pos = n - 1 - tree[cur].len - 1;            if (pos >= 0 && s[pos] == c) break;            cur = tree[cur].fail;        }        // 如果该转移已存在        if (tree[cur].next[idx]) {            last = tree[cur].next[idx];            tree[last].cnt++; // 可选：统计出现次数            return;        }        // 创建新节点        tree.push_back(Node());        int now = ++total;        tree[now].len = tree[cur].len + 2;        tree[cur].next[idx] = now;        // 设置 fail 指针        if (tree[now].len == 1) {            // 单字符回文，fail 指向空串（根1）            tree[now].fail = 1;        } else {            // 沿 fail 链向上找            cur = tree[cur].fail;            while (true) {                int pos = n - 1 - tree[cur].len - 1;                if (pos >= 0 && s[pos] == c) {                    tree[now].fail = tree[cur].next[idx];                    break;                }                cur = tree[cur].fail;            }        }        tree[now].cnt = 1; // 初始出现1次        last = now;    }    // 获取所有本质不同回文子串数量    int size() {        return total; // 不包括两个虚拟根    }};// 示例：统计不同回文子串数量int main() {    string str = "ababa";    PalindromicTree pt;    for (char c : str) {        pt.extend(c);    }    cout << "不同回文子串数量: " << pt.size() << endl; // 输出 3（"a", "b", "aba", "bab", "ababa" 共5个，但本质不同为5？实际应为5）    // 注意：本实现中 size() 返回的是节点数（即不同回文数），对于 "ababa" 应为 5    return 0;}

> 💡 提示：上述代码中 size() 返回的是本质不同的回文子串数量。对于字符串 "ababa"，回文子串有 a, b, aba, bab, ababa，共5个，因此输出应为5。

回文树 vs Manacher算法

许多初学者会问：既然有 Manacher算法替代 方案，为什么还要学回文树？关键区别在于：

应用场景

回文树特别适合解决以下问题：

• 统计字符串中本质不同的回文子串数量；
• 求每个回文子串的出现次数（需在最后进行一次 fail 树上的 DP 累加）；
• 在线处理字符串，动态回答回文相关查询；
• 作为更复杂字符串问题（如回文划分、回文自动机匹配）的基础模块。

总结

通过本教程，你已经掌握了 C++回文树 的基本原理与实现方法。回文树虽然概念稍显抽象，但一旦理解其“后缀链接”和“节点扩展”机制，就能灵活应用于各类字符串回文处理问题中。

建议你动手敲一遍代码，并尝试修改以支持大写字母或数字字符集。实践是最好的老师！

关键词回顾：C++回文树、回文自动机、Manacher算法替代、字符串回文处理