深入理解后缀自动机（Suffix Automaton）

什么是后缀自动机？

后缀自动机（Suffix Automaton）是一种有限状态自动机，它可以表示一个字符串的所有后缀。更准确地说，它能高效地表示该字符串的所有子串。它的核心优势在于：

• 构建时间复杂度为 O(n)，其中 n 是字符串长度；
• 空间复杂度也是线性的；
• 支持快速判断某字符串是否为原串的子串；
• 可用于统计不同子串数量、最长公共子串等问题。

后缀自动机的基本结构

每个状态（节点）包含以下信息：

• len：该状态能表示的最长子串长度；
• link：后缀链接（suffix link），指向另一个状态；
• next[26]：转移边，通常用于小写字母（a-z）。

理解 link 是关键：它连接的是当前状态所代表字符串的最长真后缀所对应的状态。

C语言实现步骤详解

下面我们用 C语言字符串算法 实现一个完整的后缀自动机。我们将逐步构建，并解释每一步的逻辑。

1. 定义数据结构

#define MAXN 200000  // 最大状态数，通常为 2*字符串长度#define ALPHA 26     // 字母表大小（a-z）struct State {    int len;         // 当前状态最长子串长度    int link;        // 后缀链接    int next[ALPHA]; // 转移数组};struct State st[MAXN];int sz;              // 状态总数int last;            // 最后一个状态的索引

2. 初始化自动机

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

3. 扩展自动机（添加字符）

这是最核心的部分。每次读入一个新字符 c，我们创建新状态并维护后缀链接。

void sam_extend(char c) {    int cur = sz++;                // 新建状态    st[cur].len = st[last].len + 1;        // 初始化 next 数组    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 的 link            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;}

4. 构建整个字符串的自动机

void build_sam(const char* s) {    sam_init();    for (int i = 0; s[i] != '\0'; i++) {        sam_extend(s[i]);    }}

应用示例：统计不同子串数量

利用后缀自动机，我们可以轻松计算一个字符串中不同子串的总数。公式为：

∑(st[i].len - st[st[i].link].len) ，对所有状态 i 求和

long long count_distinct_substrings() {    long long ans = 0;    for (int i = 1; i < sz; i++) {        ans += (long long)(st[i].len - st[st[i].link].len);    }    return ans;}

总结

通过本篇后缀自动机教程，你已经掌握了如何用 C 语言从零构建一个后缀自动机。虽然初看复杂，但只要理解了状态、转移和后缀链接的含义，就能灵活运用于各种字符串问题中。建议你动手敲一遍代码，加深理解。

记住，C语言后缀自动机不仅是竞赛利器，更是理解字符串本质的重要工具。继续练习，你将能解决如“最长公共子串”、“出现 k 次的最长子串”等高级问题。

希望这篇 C语言字符串算法 教程对你有所帮助！如果你有任何疑问，欢迎在评论区交流。