1. 基本概念与原理
1.1 定义与状态含义
后缀自动机（SAM，Suffix Automaton）是一种用于处理字符串子串问题的确定性有限状态机，它能够高效表示一个字符串的所有子串及其关系。状态包含的字段通常包括：转移边、最长长度、前驱链接等。通过这些信息，SAM 能在线性时间内完成子串出现统计、最长公共子串等任务。
在 SAM 中，每个状态对应一类等价的后缀集合，通常通过 len 表示该状态所能达到的最长子串长度，通过 link 指向一个更短后缀的状态，通过 next 保存转移到其他状态的字符。这样的结构让我们能够用一个二维转移表来近似表示大量子串，从而实现高效查询。
1.2 为什么要用后缀自动机
相比朴素的子串枚举，SAM 的优势在于线性构建复杂度和强大的查询能力。对于长度为 n 的字符串， SAM 的构建成本通常为 O(n)，后续的子串计数、出现次数统计等操作也能在近似常量级别内完成。使用 SAM，可以避免遍历所有子串的昂贵开销，同时在处理多种字符串相关题型时具有高度的通用性。
在实际工程中，SAM 常用于需要快速回答“某子串在文本中出现次数是多少”、“文本中是否包含某个最长子串”等问题。通过把每个状态的 occ（出现次数）等信息向上传播，可以实现对子串出现次数的快速统计。
2. 数据结构设计要点
2.1 状态结构字段
一个典型的后缀自动机状态包含若干核心字段：len（该状态代表的最長子串长度上界）、link（指向父级后缀状态的链接）、next（转移表，通常以小写字母为下标的哈希映射或数组）以及用于统计的 occ（该状态所表示子串的出现次数）等。通过这些字段，我们可以在构建阶段完成对字符串的等价类划分，并在查询阶段快速定位到目标子串。
在实现时，很多人采用固定大小的转移数组（如 next[26]），以简化实现并提升查询速度；也有场景需要动态映射以节省内存，具体选择取决于问题规模和字符集。
2.2 构造过程中的克隆
构造过程中的一个关键技巧是“克隆（clone）”操作，用于在遇到冲突时对原有状态进行分裂，使新状态能够正确地保持最长长度约束与转移路径的一致性。克隆状态的 len 等属性通常设置为冲突前状态的 len，但会复制原状态的转移信息，并将部分指向进行重定向。通过克隆，我们可以以O(1) 的时间复杂度完成状态分支，确保整個 SAM 的线性化构建。
克隆的核心思想是将一个状态的一个等价类拆分为两个子类：一个保留原有的最长长度信息，另一个用于适配新到来的字符路径。这样既保持了对子串的完整覆盖，又避免了状态之间的冗余。正确实现克隆是实现高效 SAM 的关键一步。
3. C++实现要点与完整代码
3.1 代码框架与接口
在 C++ 实现中，常见做法是实现一个 SuffixAutomaton 类，内部维护一个状态向量 st，每个状态包含 len、link、next、以及统计字段 occ。核心接口通常包括：extend(char c) 用于逐字符扩展 SAM、build(const string& s) 批量建立、count_occurrences() 对出现次数进行后向传播、以及一些查询方法如 count_substrings。
通过把字符串逐个字符传入 extend 函数，我们可以在O(n) 时间内完成整个后缀自动机的构造，并在后续阶段进行统计与查询。
3.2 构建过程与克隆操作
在实现扩展时，核心步骤包括：为新字符创建新的状态、沿着链接链回溯并更新转移、处理冲突并可能产生克隆节点，以及更新最后指针。克隆节点的引入确保了新旧状态之间的转移关系始终保持一致，且不会破坏之前已经建立的子串覆盖。
实现细节需要注意：初始化时所有转移设置为无效值（如 -1），以及在克隆时复制目标状态的转移集合，同时将克隆及相关状态的 len、link、occ 等字段进行正确调整。完成后，last 指针应指向当前字符串末尾对应的状态。
// 简化版本的 C++ 后缀自动机示例（仅作教学用途）
#include
using namespace std;struct SuffixAutomaton {struct State {int len; // 该状态表示的最长子串长度int link; // 后缀链接int next[26]; // 转移表，假设小写字母long long occ; // 出现次数统计State() : len(0), link(-1), occ(0) {fill(begin(next), end(next), -1);}};vector st;int last;SuffixAutomaton(int maxlen = 100000) {st.reserve(2 * maxlen);st.push_back(State()); // 初始状态last = 0;}void extend(char c) {int cur = (int)st.size();st.push_back(State());st[cur].len = st[last].len + 1;st[cur].occ = 1;int p = last;int ch = c - 'a';for (; p != -1 && st[p].next[ch] == -1; p = st[p].link)st[p].next[ch] = cur;if (p == -1) {st[cur].link = 0;} else {int q = st[p].next[ch];if (st[p].len + 1 == st[q].len) {st[cur].link = q;} else {int clone = (int)st.size();st.push_back(st[q]);st[clone].len = st[p].len + 1;st[clone].occ = 0;for (; p != -1 && st[p].next[ch] == q; p = st[p].link)st[p].next[ch] = clone;st[q].link = st[cur].link = clone;}}last = cur;}void build(const string &s) {for (char c : s) extend(c);}void count_occurrences() {vector order(st.size());iota(order.begin(), order.end(), 0);sort(order.begin(), order.end(), [&](int a, int b) { return st[a].len > st[b].len; });for (int v : order) {if (st[v].link != -1)st[st[v].link].occ += st[v].occ;}}// 统计任意模式字符串 t 在文本中的出现总数（通过状态机进行遍历）long long count_substrings(const string &t) {int v = 0;int l = 0;long long ans = 0;for (char c : t) {int ch = c - 'a';if (st[v].next[ch] != -1) {v = st[v].next[ch];++l;} else {while (v != -1 && st[v].next[ch] == -1)v = st[v].link;if (v == -1) {v = 0;l = 0;} else {l = st[v].len + 1;v = st[v].next[ch];}}ans += l;}return ans;}
};
4. 常见应用与题型
4.1 子串出现次数统计
利用 occ 字段以及后向传播，我们可以快速得到任意子串在原文本中出现的次数。通过在构建阶段对每个状态的出现次数初始化为 1，并在 count_occurrences() 中向上累积，可以得到每个等价类对应的准确出现次数。这是解决“某子串在文本中出现了多少次”的常见思路。
在实际竞赛题中，常见做法是先构建 SAM，再对目标文本进行遍历，记录最长匹配长度及累计出现次数，最终得到统计结果。该过程的时间复杂度接近线性，适用于大规模字符串。
4.2 最长公共子串（LCS）
SAM 可用于求解两个字符串的最长公共子串问题。通过将一条字符串构造成 SAM，另一条字符串在 SAM 上进行遍历，记录当前匹配长度并维护全局最大值，即可得到 LCS 的长度。相较于后缀数组等方法，SAM 在实现上往往更直观，且在某些场景具有更优的常数项。
在实际实现中，通常需要同时考虑边界情况和重复子串的处理，以确保在不同输入下都能正确给出结果。通过维护变量 v 与 l，可以逐步扩大匹配并更新全局最大值。
4.3 实战技巧与常见陷阱
在实现时，注意字符集范围和转移表示方式的选择。若文本包含非小写字母，需要扩展 next 的映射结构，或采用哈希表/映射来处理多字符集。其次，克隆节点的正确性直接影响到后续的查询正确性，务必在构造阶段严格按标准流程进行。最后，在统计阶段，count_occurrences() 的后向传播是实现子串出现次数统计的关键步骤。
此外，充分利用对称性与局部特性：许多题目只需要对小写字母进行处理时，固定长度的转移表能显著提升性能，且内存使用更易控控。
