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

什么是后缀自动机？

后缀自动机是一个有向无环图（DAG），其中每个节点代表字符串的一个等价类（endpos 等价类），每条边代表添加一个字符后的状态转移。它的核心优势在于：

• 构建时间复杂度为 O(n)，n 为字符串长度；
• 空间复杂度也是 O(n)；
• 可以高效回答关于子串的各种问题。

在 C++字符串处理 中，后缀自动机是高级字符串算法的重要组成部分。

后缀自动机的基本结构

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

• len：该状态能表示的最长字符串长度；
• link：后缀链接（suffix link），指向另一个状态；
• next[26]：字符转移数组（假设只处理小写字母）。

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

我们将逐步构建一个支持动态添加字符的后缀自动机。以下是完整代码：

#include <iostream>#include <cstring>#include <vector>using namespace std;const int MAXLEN = 100000; // 最大字符串长度const int ALPHA = 26;      // 字符集大小（a-z）struct State {    int len;          // 当前状态最长字符串长度    int link;         // 后缀链接    int next[ALPHA];  // 转移边    State() {        len = 0;        link = -1;        memset(next, -1, sizeof(next));    }};struct SuffixAutomaton {    vector<State> st;    int last;         // 当前最后一个状态    int sz;           // 状态总数    SuffixAutomaton() {        st.resize(2 * MAXLEN);        st[0] = State();        st[0].len = 0;        st[0].link = -1;        sz = 1;        last = 0;    }    void extend(char c) {        int cur = sz++;        st[cur] = State();        st[cur].len = st[last].len + 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 {                // 克隆节点                int clone = sz++;                st[clone] = st[q];                st[clone].len = st[p].len + 1;                while (p != -1 && st[p].next[c - 'a'] == q) {                    st[p].next[c - 'a'] = clone;                    p = st[p].link;                }                st[q].link = st[cur].link = clone;            }        }        last = cur;    }    // 示例：计算不同子串数量    long long countDistinctSubstrings() {        long long total = 0;        for (int i = 1; i < sz; i++) {            total += st[i].len - st[st[i].link].len;        }        return total;    }};// 使用示例int main() {    string s = "ababa";    SuffixAutomaton sam;    for (char c : s) {        sam.extend(c);    }    cout << "不同子串数量: " << sam.countDistinctSubstrings() << endl;    return 0;}

代码详解

1. State 结构

每个状态保存长度、后缀链接和转移边。初始化时，所有转移设为 -1（无效）。

2. extend 函数

这是构建自动机的核心函数。每次添加一个字符，可能创建新状态或克隆已有状态。关键逻辑包括：

• 沿后缀链接回溯，设置新字符的转移；
• 处理需要克隆的情况（当发现一个状态的转移不满足长度条件时）；
• 更新后缀链接。

3. 应用：统计不同子串数量

利用后缀自动机的性质：每个状态代表若干子串，其数量为 len[i] - len[link[i]]。累加即可得到总的不同子串数。

为什么学习 C++ 后缀自动机？

掌握 C++后缀自动机 不仅能提升你对 字符串算法 的理解，还能在竞赛（如 ACM、Codeforces）和实际工程（如文本索引、DNA 序列分析）中发挥巨大作用。它是高级 C++字符串处理 技术的基石之一。

总结

本文通过清晰的步骤和完整的 C++ 代码，带你实现了后缀自动机。我们讲解了其结构、构建过程以及一个经典应用。希望你能在此基础上继续探索更多 后缀自动机实现 的高级技巧，如求最长公共子串、子串出现次数等。

动手实践是掌握算法的关键！尝试修改代码，处理大写字母或 Unicode 字符，加深理解。