C语言回文树详解（从零开始掌握回文自动机的实现与应用）

为什么使用回文树？

相比暴力枚举（O(n²)）或Manacher算法（仅求最长回文），回文树可以在 O(n) 时间内完成以下任务：

• 统计所有不同回文子串的数量
• 记录每个回文出现的次数
• 支持在线添加字符并动态维护回文信息

这使得它成为解决高级字符串问题（如LeetCode、Codeforces题目）的利器。

C语言回文树的核心结构

我们先定义回文树的节点结构：

typedef struct Node {    int len;           // 当前回文串的长度    int fail;          // fail指针，指向最长真回文后缀    int cnt;           // 该回文串出现的次数（可选）    int next[26];      // 子节点，假设只处理小写字母} Node;Node tree[MAX_N];     // 节点数组int last;             // 最后插入字符对应的回文节点int sz;               // 当前节点总数char s[MAX_N];        // 输入字符串int n;                // 字符串长度

初始化回文树

我们需要创建两个初始根节点：

void init() {    // 清空树    memset(tree, 0, sizeof(tree));        // 根0：长度为-1（奇数回文起点）    tree[0].len = -1;    tree[0].fail = 0; // 自环        // 根1：长度为0（偶数回文起点）    tree[1].len = 0;    tree[1].fail = 0; // 指向根0        sz = 2;           // 已有2个节点    last = 0;         // 初始last设为0    n = 0;            // 字符串长度为0}

核心函数：get_fail

在插入新字符时，我们需要沿着 fail 链向上跳，直到找到可以扩展的位置：

// 从当前last节点向上跳fail，直到s[n - tree[cur].len - 1] == s[n]int get_fail(int cur) {    while (s[n - tree[cur].len - 1] != s[n]) {        cur = tree[cur].fail;    }    return cur;}

插入字符并构建回文树

逐个读入字符，动态扩展回文树：

void extend(char c) {    s[++n] = c; // 注意：s[0]不使用，从s[1]开始    int cur = get_fail(last);    int ch = c - 'a';        if (!tree[cur].next[ch]) {        // 创建新节点        int now = sz++;        tree[now].len = tree[cur].len + 2;                // 设置fail指针        int tmp = tree[cur].fail;        tmp = get_fail(tmp);        tree[now].fail = tree[tmp].next[ch];                // 如果fail未设置（比如指向不存在的节点），默认指向根1（空串）        if (tree[now].fail == 0) tree[now].fail = 1;                tree[cur].next[ch] = now;    }        last = tree[cur].next[ch];    tree[last].cnt++; // 记录出现次数}

完整示例：统计不同回文子串数量

下面是一个完整的C语言程序，读入一个字符串并输出其中不同回文子串的总数：

#include <stdio.h>#include <string.h>#define MAX_N 100010typedef struct Node {    int len, fail, cnt, next[26];} Node;Node tree[MAX_N];int last, sz, n;char s[MAX_N], input[MAX_N];void init() {    memset(tree, 0, sizeof(tree));    tree[0].len = -1; tree[0].fail = 0;    tree[1].len = 0;  tree[1].fail = 0;    sz = 2; last = 0; n = 0;}int get_fail(int cur) {    while (s[n - tree[cur].len - 1] != s[n])        cur = tree[cur].fail;    return cur;}void extend(char c) {    s[++n] = c;    int cur = get_fail(last);    int ch = c - 'a';    if (!tree[cur].next[ch]) {        int now = sz++;        tree[now].len = tree[cur].len + 2;        int tmp = tree[cur].fail;        tmp = get_fail(tmp);        tree[now].fail = tree[tmp].next[ch];        if (tree[now].fail == 0) tree[now].fail = 1;        tree[cur].next[ch] = now;    }    last = tree[cur].next[ch];    tree[last].cnt++;}int main() {    init();    scanf("%s", input);    for (int i = 0; input[i]; i++) {        extend(input[i]);    }    printf("不同回文子串数量: %d\n", sz - 2); // 减去两个根节点    return 0;}

总结

通过本教程，你已经掌握了回文自动机实现的基本原理和C语言编码技巧。回文树虽然初看复杂，但只要理解了 fail 指针的作用和两个根节点的设计思想，就能轻松驾驭这一强大的字符串算法教程中的高级工具。

建议你动手敲一遍代码，尝试修改以支持大小写字母或数字，并思考如何利用 cnt 字段统计每个回文的实际出现次数。掌握这项技术后，你将能高效解决各类涉及回文的编程难题！

如果你正在学习数据结构与算法，不妨将回文结构C语言作为进阶项目，深入理解其在线性时间内的神奇效率。