深入理解C语言后缀自动机（从零开始掌握高效字符串匹配技术）

为什么使用 C 语言实现？

C 语言提供了对内存和指针的精细控制，非常适合实现底层数据结构。通过手写 C语言字符串处理逻辑，你能更深入理解后缀自动机的工作原理，同时提升算法能力。

核心概念解析

• 状态（State）：每个状态代表一组 endpos 等价类（即子串结束位置集合相同的子串）。
• 转移（Transition）：从一个状态通过某个字符转移到另一个状态。
• 后缀链接（Suffix Link）：指向当前状态所代表子串的最长真后缀对应的状态。

C语言后缀自动机实现步骤

我们将逐步构建一个支持动态添加字符的后缀自动机。以下是关键结构体定义：

#define MAXN 200000  // 最大字符数#define ALPHA 26     // 假设只处理小写字母struct State {    int len;               // 当前状态代表的最长子串长度    int link;              // 后缀链接    int next[ALPHA];       // 转移数组};struct State st[MAXN * 2]; // 状态数组，最多 2n 个状态int sz;                    // 当前状态总数int last;                  // 当前字符串最后一个字符对应的状态

初始化函数：

void sam_init() {    // 初始化初始状态（状态0）    st[0].len = 0;    st[0].link = -1;    for (int i = 0; i < ALPHA; i++)        st[0].next[i] = -1;    sz = 1;    last = 0;}

添加字符的核心函数（后缀自动机实现的关键）：

void sam_extend(char c) {    int cur = sz++;                     // 创建新状态    st[cur].len = st[last].len + 1;    for (int i = 0; i < ALPHA; i++)        st[cur].next[i] = -1;    int p = last;    // 沿着后缀链接向上遍历，设置转移    while (p != -1 && st[p].next[c - 'a'] == -1) {        st[p].next[c - 'a'] = cur;        p = st[p].link;    }    if (p == -1) {        st[cur].link = 0;    } else {        int q = st[p].next[c - 'a'];        if (st[p].len + 1 == st[q].len) {            st[cur].link = q;        } else {            // 克隆状态 q            int clone = sz++;            st[clone].len = st[p].len + 1;            for (int i = 0; i < ALPHA; i++)                st[clone].next[i] = st[q].next[i];            st[clone].link = st[q].link;            // 更新 q 和 cur 的后缀链接            st[q].link = st[cur].link = clone;            // 修正之前的转移            while (p != -1 && st[p].next[c - 'a'] == q) {                st[p].next[c - 'a'] = clone;                p = st[p].link;            }        }    }    last = cur;}

完整使用示例

下面是一个完整的程序，读入一个字符串并构建其后缀自动机：

#include <stdio.h>#include <string.h>// ... 上面定义的结构体和函数 ...int main() {    char s[100005];    scanf("%s", s);        sam_init();    for (int i = 0; s[i]; i++) {        sam_extend(s[i]);    }        printf("后缀自动机构建完成！总状态数：%d\n", sz);    return 0;}

应用场景与优势

掌握 后缀自动机教程中的知识后，你可以解决以下问题：

• 统计字符串中不同子串的数量（答案为 Σ(len[i] - len[link[i]])）
• 查找两个字符串的最长公共子串
• 快速判断某字符串是否为原串的子串（时间复杂度 O(m)，m 为查询串长度）

总结

通过本教程，你已经掌握了 C语言后缀自动机的基本原理和实现方法。虽然初次接触可能觉得复杂，但只要理解状态、转移和后缀链接的关系，就能灵活运用这一强大工具。建议多动手调试代码，观察状态变化，加深理解。

继续练习吧！尝试用它解决实际问题，你会发现 C语言字符串处理的世界远比想象中精彩。