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

核心概念解析

• 状态（State）：每个状态代表一组 endpos 等价的子串。endpos(s) 是子串 s 在原字符串中所有结束位置的集合。
• 转移（Transition）：从一个状态通过字符 c 转移到另一个状态，表示当前子串可以扩展字符 c。
• 后缀链接（Suffix Link）：指向当前状态所代表子串的最长真后缀对应的状态，用于构建自动机时回溯。

C++后缀自动机的实现步骤

我们采用在线增量构造法：逐个添加字符，动态维护自动机结构。以下是关键变量定义：

struct State {    int len;        // 当前状态代表的最长子串长度    int link;       // 后缀链接    int next[26];   // 转移数组（假设只处理小写字母）};const int MAXLEN = 100000;State st[MAXLEN * 2];int sz, last;  // sz: 状态总数, last: 当前字符串结尾对应的状态

初始化

void sam_init() {    // 初始化初始状态（空串）    st[0].len = 0;    st[0].link = -1;    memset(st[0].next, -1, sizeof(st[0].next));    sz = 1;    last = 0;}

添加字符（核心函数）

每次添加一个字符 c，执行以下步骤：

1. 创建新状态 cur，长度为 last.len + 1
2. 从 last 开始沿后缀链接向上跳，设置未定义的转移指向 cur
3. 若跳到根仍未找到转移，则设置 cur 的后缀链接为根
4. 否则，设 p 为停止的位置，q 为 p 通过 c 转移到的状态
5. 若 q.len == p.len + 1，则 cur.link = q
6. 否则，需克隆 q 状态（称为 clone），调整相关链接

void sam_extend(char c) {    int cur = sz++;    st[cur].len = st[last].len + 1;    memset(st[cur].next, -1, sizeof(st[cur].next));        int p = last;    // 步骤2：沿后缀链接向上，设置转移    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;  // 步骤3    } else {        int q = st[p].next[c - 'a'];        if (st[p].len + 1 == st[q].len) {            st[cur].link = q;  // 步骤5        } else {            // 步骤6：克隆状态 q            int clone = sz++;            st[clone].len = st[p].len + 1;            memcpy(st[clone].next, st[q].next, sizeof(st[q].next));            st[clone].link = st[q].link;                        // 更新 q 和 cur 的后缀链接            st[q].link = st[cur].link = clone;                        // 修正之前指向 q 的转移            while (p != -1 && st[p].next[c - 'a'] == q) {                st[p].next[c - 'a'] = clone;                p = st[p].link;            }        }    }    last = cur;}

完整使用示例

#include <iostream>#include <cstring>using namespace std;// ... 上述结构体和函数定义 ...int main() {    string s = "abcbc";    sam_init();    for (char c : s) {        sam_extend(c);    }        cout << "后缀自动机构建完成！总状态数: " << sz << endl;    // 此时可进行各种查询，如不同子串数量 = Σ(st[i].len - st[st[i].link].len)    long long distinct_substrings = 0;    for (int i = 1; i < sz; i++) {        distinct_substrings += st[i].len - st[st[i].link].len;    }    cout << "不同子串数量: " << distinct_substrings << endl;    return 0;}

应用场景与优势

后缀自动机是解决复杂字符串算法问题的利器，典型应用包括：

• 统计不同子串数量（如上例）
• 查找最长重复子串
• 多字符串的最长公共子串（结合广义后缀自动机）
• 子串出现次数统计（需额外拓扑排序）

相比后缀数组或后缀树，后缀自动机在C++字符串处理中具有代码简洁、常数小、支持在线构建等优势，是竞赛和工程中的优选方案。

总结

通过本教程，你已经掌握了C++后缀自动机的基本原理与实现方法。虽然初次接触可能觉得抽象，但只要理解了状态、转移和后缀链接的作用，就能灵活运用这一强大工具。建议动手实现并尝试解决 LeetCode 或 Codeforces 上的相关题目，巩固所学知识！

关键词回顾：C++后缀自动机、字符串算法、后缀自动机实现、C++字符串处理。