浅谈后缀自动机
写在前面：好久没有写出一些优质（本来也就不优质）的文章了，主要是最近学业太忙，连之前的笔误也没来得及修改，在此致歉。当然，消失了这么长时间我觉得我还是学有所获的，比如学会了LCT,TopTree,SAM,PAM以及计算几何这些神奇的东西，当然我后面也都会抽时间把它们写下来，不过对我而言，最难的肯定属于SAM。当然，痛苦和收获是成正比例的（装什么13,SAM之所以苦难，主要是因为它太全能了，比如什么字符串匹配（KMP)，最长公共子串（LCS)，本质不同的子串计数，第k大子串输出等等等，SAM全部适用，而且时间复杂度均在 \(O(n)\) 到 \(O(n + m)\) 之间，是非常amazing的的数据结构啊。好了，说了这么多，我们，直接开始！
从基础开始
为了能够讲清楚后缀自动机的基本原理，我们先从最简单的字符串 s = "abab" 开始。
1.子串？后缀？
我们知道，后缀自动机顾名思义，就是由后缀构成的自动机（废话），而后缀和子串呢，在我学的时候，总是被搅得一头雾水不知所措，所以把这两个东西分开说说：
[*]子串(Substring)：从字符串任意位置开始之后连续的一段我们称之为子串，对于 \(S\) 的子串 \(Z\) 满足以下性质：
[*]\(Z \in S\) ,这不难理解，从 \(S\) 里面揪出来的字符，自然就属于 \(S\) 。
2.子串的occurrences可以重叠，例如 "ababa" 的子串 "aba" 出现位置是 \(\) 与 \(\) 。
3.长度为 \(n\) 的字符串一共有 \(\frac{n \times{n + 1}}{2}\) 个子串，这也不难理解，我们小学二年级就学过的组合数学，我们知道，一个子串的开头 \(i\) 和结尾 \(j\) 必须满足 \(i \le j\) ，可以写成组合数学的形式就是：
\
[*]后缀（Suffix）
终于说到后缀了吗？你可能认为这很简单，当然事先说好，这只是开始，我们马上难度飙升（从第 \(3\) 部分开始）。为了学习后缀自动机，我们一定要了解，对于后缀的一些特殊性质：
[*]唯一性：对于每一个位置都有唯一的后缀，因为后缀是从一个位置 \(i\) 一直连接到末尾的一种特殊子串，所以存在唯一性。
2.覆盖性：这个比较有意思，我们可以证明，对于任意一个子串 \(Z\) ，是某一个后缀得到真前缀，这非常好理解，我们假设 \(Z\) 的开头为 \(i\) ，直接选择开头为 \(i\) 的后缀就可以了。
3.包含性：对于一个字符串 \(s\) 有后缀 \(s\) 和 \(s\) 且满足\(i \le j\) ，则后者是前者的后缀，举个例子,s="banana" 其中 "nana" 是 "banana" 的后缀。
看到这里了吗？你学会后缀自动机~最简单的部分啦！接下来难度飙升，做好准备！
2.引入FSA
有限状态自动机（Finite State Automaton , FSA)，是不是听起来就高级？错啦，其实一点都不难（假的）。
[*]2.1 有限状态自动机？
我们认为，有限FSA有以下几个部分构成：
[*]状态集合 \(Q\) ，表示系统可能处于的所有状态。
[*]字符集 \(\sum\) ， 表示输入的字符串符号集合。
[*]转移函数 \(\delta\) ，给定当前状态和输入符号，决定下一个状态是什么。
[*]初始状态 \(q_0\) ，自动机一开始的状态。
[*]终止集合 \(F\) ，某些状态被标记为“接受状态”。
[*]2.2 FSA \(\to\) SAM的一些特殊性质
[*]确定性：每个状态对同一输入符号只有 唯一转移 ， 这很重要！
[*]最小性: SAM在所有DFA中是最小的，能够存下所有子串而且状态数最少，最多 \(2n - 1\) 个状态 , \(4n - 3\) 条边。
[*]后缀连接：这个后面再说
总之，FSA一定是一个DAG，这很重要（大声）。
3. 先说点别的
这不是在开玩笑，是的，说SAM必须要先说它最重要的核心逻辑endpos，对于一个子串 \(Z\) , 其endpos 是它所有结束的位置，例如对于 S="ababa" 的子串 Z="a" ，那么其endpos $ = { 0 , 2 , 4 }$ 。那么都说了endpos 了，必须把等价类也交出来了，是的，我们规定：对于一个字符串 \(S\) ，子串 \(i\) 与 \(j\) 是等价类当且仅当 \(endpos(i) = endpos(j)\) 。比如 s = "abab" 中：
[*]子串 "ab" 的 enpos = {2 , 4}
[*]子串 "b" 的 endpos = {2 , 4}
那么我们称 "ab" 和 "b" 是一个等价类。学过SAM的同学肯定知道，这些等价类是属于同一个状态的，没错，可我还是不想写那个部分，我们还要说一些endpos的特殊性质。同属一个等价类中的所有子串长度是连续的，而且对于一个等价类集合 \(D\) 存在：若其中一个子串的长度大于等于另一个字串的长度，那么后者是前者的后缀，我们还是拿上面那个例子说事，此时的 \(D\) 有 "ab" 和 "b" 两个子串，其中前者长度大于后者，所以后者是前者的后缀而且这个 \(D\) 的长度在 \(\) 而且连续，如何证明这个性质是正确的？我们尝试使用字符串匹配的思路解释，若对于一个后缀\(i\) 是另一个后缀 \(j\) 的后缀，容易证明 \(endpos(j) \in endpos(i)\) ， 这样就很好理解了，当然这个性质解释了我们后面一个非常重要的东西Parent Tree。还有一个性质，就是对于一个长度为 \(n\) 的字符串 \(S\) 的所有等价类数量不超过 \(2n\) ， 这后面会说。
3.母树
母树（Parent Tree) ，讲解这个之前，我们需要先引入一个东西 \(\sigma\) ，它是一个虚拟的东西用来充当根节点，对于 \(\sigma\) 的endpos集合大小为 \(n\) 且每个位置都包含，为什么要这么干呢？对于母树，相当于把我们上面所说的endpos性质1变成了树的形式，在母树上，任何一个父节点 \(i\) 满足其所有子节点 \(j\) 满足 \(endpos(j) \in endpos(i)\) ，也就是说， \(i\) 的子节点全部是 \(i\) 的后缀。通过以上性质可知，Parent Tree 的高度是 \(n\) 级别的，为了帮助理解，我们对于字符串 S = "abcabdf" 做一颗母树：
以下是字符串 S = "abcabdf" 的 Parent树（后缀链接树） 的构建步骤和图表：
graph TD %% 根节点（空串） 0["0: endpos={0,1,2,3,4,5,6}\n子串: ε"] %% 第一层节点 0 --> 1["1: endpos={1,4}\n子串: a"] 0 --> 7["7: endpos={6}\n子串: f"] 0 --> 3["3: endpos={3}\n子串: c"] 0 --> 8["8: endpos={5}\n子串: d"] %% 第二层节点 1 --> 2["2: endpos={2,5}\n子串: ab, b"] 3 --> 4["4: endpos={4}\n子串: abc, bc"] 8 --> 9["9: endpos={6}\n子串: df"] %% 第三层节点 2 --> 5["5: endpos={5}\n子串: abcab, bcab, cab"] 4 --> 6["6: endpos={6}\n子串: abcabd, bcabd, cabd"]但是这么看起来，母树的时间还是空间复杂度都很优秀了呀？是不是可以收手啦？当然不行！观察上面的母树一共 \(10\) 个节点，而我们的SAM呢？也要十个节点，这个例子不是很好，大家可以尝试使用 S = "abcbc" 来举例子，最后的结果可以表明，SAM终究还是优化了 \(3\) 个节点，我们来看一下SAM:
graph LR %% 初始状态 0((0)) %% 单字符状态 0 --a--> 1((1)) 0 --b--> 2[] 0 --c--> 3((3)) 0 --d--> 8((8)) 0 --f--> 7((7)) %% 多字符状态 1 --b--> 2 2 --c--> 4((4)) 4 --a--> 5[] 5 --b--> 6[] 5 --d--> 9((9)) 8 --f--> 9 %% 后缀链接（虚线） 2 -.-> 1 4 -.-> 2 5 -.-> 4 6 -.-> 5 9 -.-> 8欸，我们发现这个SAM好像有什么特殊的好东西，把所有虚线拎出来，我们发现，刚好构成了Parent Tree , 这是怎么一回事？在此之前，先把 Suffix Links 说完！
4.后缀连接
后缀链接（Suffix Links) ，表示对于一个非 \(\sigma\) 的状态 \(u\) ，其后缀连接连接到SAM中\(u\) 的最长真后缀所在的状态，我们定义真后缀为不等于 \(u\) 的后缀。那么这个后缀链接有什么用处啊？我们将在后面的构造SAM中说明，先说一些特殊性质：
1. 树形结构（Parent 树）
[*]性质：所有后缀链接构成一棵以初始状态 $ \text{state}_0 $（空串）为根的树，称为 Parent 树 或 后缀链接树。
[*]原因：
[*]每个非初始状态有且只有一个后缀链接（函数性质）。
[*]沿后缀链接跳转最终必然到达初始状态（无环）。
[*]示例：
graph TD 0((0)) --> 1((1)) 0 --> 3((3)) 1 --> 2((2)) 2 --> 4((4))2. 子串长度的严格递减
[*]性质：若 $ \text{link} = v $，则 $ \text{len}(v) < \text{len}(u) $。
[*]解释：
[*]$ v $ 是 $ u $ 的最长真后缀，因此 $ v $ 的子串长度必然更短。
3. endpos 的包含关系
[*]性质：若 $ \text{link} = v $，则 $ \text{endpos}(u) \subseteq \text{endpos}(v) $。
[*]推论：
[*]在 Parent 树中，子节点的 endpos 是父节点的子集。
4. 后缀链接与状态分裂
[*]性质：在 SAM 的增量构造过程中，后缀链接指导状态的克隆（分裂）。
[*]过程：
[*]当插入字符 $ c $ 导致 endpos 不一致时，需克隆状态。
[*]新状态的 link 指向原 link 的目标，并更新相关转移。
5. 叶子节点的后缀特性
[*]性质：Parent 树的叶子节点对应原字符串的 完整后缀。
[*]应用：
[*]通过遍历叶子节点，可以枚举所有后缀。
6. 线性跳转优化
[*]性质：通过后缀链接跳转，可将子串匹配的时间复杂度均摊为 $ O(1) $。
很全面了吧，母树真的不难吧，来吧，开始学习真正的SAM
5. 构建SAM
SAM（Suffix Automaton ， SAM) ， 在我们前面所提到的所有信息中，我们主要讲述了SAM的全能以及一些特殊性质，以下是一些你必须要知道的规则：
[*]起点和终点之间的边代表给当前字符串添加一个字符。
[*]从根到任意点的路径是 \(S\) 的一个子串。
[*]保证每一个节点上的点全部属于一个等价类。
[*]点和点之间要有正确的父子关系，也就是说，到达 \(i\) 的所有子串长度必须大于 \(i\) 的父亲的子串长度，而且保证以 \(i\) 为父亲的所有子节点均让 \(i\) 是当前子节点子串后缀。
接下来的学习，我们会连图带着文本一起学，一起来看一个例子 S="abab" ：
[*]初始化，我们放一个根节点 \(0\) ，代表着空串，方便构建后缀自动机。
graph LR 0((0: len=0, link=null))
[*]接下来，我们需要插入 a 这一个新状态，此时我们的 last 指针指向 \(0\) ，此时SAM上面没有子串，那么就设置一个新状态 \(1\) ，令 \(1\) 的 len 为 1，顺带提一嘴，我们的len表示当前节点中最长子串,link表示后缀连接：
graph LR 0((0)) --a--> 1((1: len=1, link=0))此时last指向 \(1\) 。
3. 插入一个 b：
设置一个新的状态 2 ， 因为当前字符串中有 {"a" , "") 这两个子串 ，意味着会产生 {"ab" , "b"} 两个子串 "ab" 好说，但是 "b" 怎么办呢？还记得我们学过的后缀连接吗，没错，这个东西将在这里发挥用处，我们知道，不是对于每一个节点都要直接连接向当前节点的，对于要插入的一个字符 \(c\) 以及它的父亲 \(i\) ， 我们知道，对于 \(c\) 可能产生的所有子串是每一个对于当前字串存在的 \(i\) 的后缀并拼接上 \(c\) 的字符串 ， 是不是有点难懂了，没事，你可以先记下来，后面练多了就知道了。我们观察以上这句话和后缀链接的性质，没错，就是沿着后缀连接向上跳，当且仅当当前节点的后缀连接不是不存在而且当前节点也不存在子节点 \(c\) ，我们就将 \(c\) 添加到当前节点的儿子，那有的人就好奇了，欸为什么我们不能把 \(c\) 连接到已经有 \(c\) 的节点上呢？首先就是人家都有 \(c\) 了，没办法往上面去挂。还有一个重要的原因就是我们需要连后缀链。是的，对于当前节点的 \(c\) 儿子， 我们认定当其len 正好是它父亲的长度 + 1 的时候，我们就让插入的 \(c\) 节点link为这个 \(c\) 儿子，原因很好解释，因为根据endpos的性质可知：这个子节点是它父亲的直接拓展，这个子节点的子串集合是最简单的了，说白了就是不可能有别的子串在当前节点“捣乱”了，可以放心连接。
graph LR 0((0)) --a--> 1((1)) 0 --b--> 2((2: len=2, link=0)) 1 --b--> 2
[*]还要再插入一个 a , 没什么好说的，直接做就好了：
graph LR 0((0)) --a--> 1((1)) 0 --b--> 2((2)) 1 --b--> 2 2 --a--> 3((3: len=3, link=1)) 1 --a--> 3
[*]也是直接操作就可以了，没什么好说的：
graph LR 0((0)) --a--> 1((1)) 0 --b--> 2((2)) 1 --b--> 2 2 --a--> 3((3)) 3 --b--> 4((4: len=4, link=2)) 1 --a--> 3 2 --b--> 4其实这个例子举得很失败，但是当我们拿出 S="abcb" 的SAM 的时候，一切都变了
graph LR 0 --a--> 1 0 --b--> 5 1 --b--> 5 5 --c--> 3 3 --b--> 4 5 --b--> 4 2 --c--> 3 1 -.-> 0 2 -.-> 5 3 -.-> 0 4 -.-> 5 5 -.-> 0欸，这个 \(5\) 是怎么来的，不是只有四个字符吗，没错，它分裂了，对于我们上面讲的，插入最后一个 b 的时候，我们跳着后缀链发现这个节点的 b 号儿子存在而且其len不为当前节点的len + 1 的时候，说明这个endpos有更长的子串，我们没有办法直接连接，不然如图所示：
graph LR 0 --a--> 1 1 --b--> 2 0 --b--> 2 0 --c--> 3 2 --c--> 3 3 --b--> 4此时我们的节点 \(2\) 上发生了冲突，是的节点 \(2\) 上的子串本来是 {"ab" , "a"} , 我们发现他们的endpos是不等价的，此时我们就需要把 \(2\) 的一些子串单独拎出来，也就是 b 给拎出来（也就是把len小于等于插入当前字符子串最长真后缀的所有子串拎出来） ， 这样子子串被分成两部分，不再互相干扰，我们再克隆一下原来节点的状态就可以了，so sample 有没有？
好了，恭喜你，学会了后缀自动机，也就是SAM的基本操作了，要彻底学会它，你还要学会一些基本的应用。
6.SAM的基本应用
我说过的，SAM是基本全能的amazing算法，它甚至可以代替我们的KMP!
以下是 后缀自动机（SAM）的基本应用 及其实现方法，涵盖字符串匹配、子串统计、最长公共子串等经典问题，附代码模板和关键分析：
1. 检查子串是否存在
问题：判断模式串 P 是否是 S 的子串。
方法：在 SAM 上从初始状态沿 P 的字符转移，若全程无阻塞则存在。
代码（C++）：
bool is_substring(SAM &sam, const string &P) {
int u = 0; // 初始状态
for (char c : P) {
if (!sam.st.trans.count(c)) return false;
u = sam.st.trans;
}
return true;
}复杂度：O(|P|)。
2. 统计不同子串数量
问题：计算 S 中本质不同的子串个数。
方法：利用 SAM 的状态性质，每个状态贡献 len - len] 个新子串。
公式：
\[\text{ans} = \sum_{u} (\text{len} - \text{len}[\text{link}])\]
代码：
int count_distinct_substrings(SAM &sam) {
int res = 0;
for (int u = 1; u < sam.st.size(); u++) {
res += sam.st.len - sam.st.link].len;
}
return res;
}复杂度：O(n)。
3. 计算子串出现次数
问题：统计某个子串 P 在 S 中的所有出现次数。
方法：
[*]预处理每个状态的 cnt（通过 Parent 树 DFS 或拓扑排序计算）。
[*]在 SAM 上找到 P 对应的状态 u，其 cnt 即为答案。
代码：
void preprocess_count(SAM &sam) {
vector<int> cnt(sam.st.size(), 1);
// 按 len 倒序拓扑排序（Parent 树的逆序）
vector<int> order(sam.st.size());
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {
return sam.st.len > sam.st.len;
});
for (int u : order) {
if (sam.st.link != -1) {
cnt.link] += cnt;
}
}
sam.cnt = cnt;
}
int substring_count(SAM &sam, const string &P) {
int u = 0;
for (char c : P) {
if (!sam.st.trans.count(c)) return 0;
u = sam.st.trans;
}
return sam.cnt;
}复杂度：预处理 O(n)，查询 O(|P|)。
4. 寻找最长重复子串
问题：找到 S 中最长的至少出现两次的子串。
方法：在 Parent 树中寻找最深的满足 cnt ≥ 2 的节点。
代码：
string longest_repeated_substring(SAM &sam) {
int max_len = 0, best_u = -1;
for (int u = 1; u < sam.st.size(); u++) {
if (sam.cnt >= 2 && sam.st.len > max_len) {
max_len = sam.st.len;
best_u = u;
}
}
// 从 best_u 回溯构造子串
string res;
int u = best_u;
while (u != 0) {
for (auto : sam.st.link].trans) {
if (v == u) {
res.push_back(c);
break;
}
}
u = sam.st.link;
}
reverse(res.begin(), res.end());
return res;
}复杂度：O(n)。
5. 多字符串最长公共子串（LCS）
问题：求多个字符串的最长公共子串。
方法：构建广义 SAM，对每个状态维护来自每个字符串的匹配次数。
代码框架：
string longest_common_substring(const vector<string> &strs) {
GeneralizedSAM gsam;
for (const string &s : strs) {
gsam.extend(s);
}
// 统计每个状态在所有字符串中的出现情况
// 返回满足全覆盖条件的最长状态对应的子串
// （具体实现需根据广义SAM的构造调整）
}复杂度：O(\sum |S_i|)。
6. 字典序第 k 小子串
问题：求 S 的所有子串中字典序第 k 小的子串。
方法：在 SAM 的 DAG 上动态规划预处理每个状态的路径数，然后按字典序 DFS。
代码逻辑：
void preprocess_kth(SAM &sam) {
vector<int> dp(sam.st.size(), 1);
// 按 len 倒序拓扑排序
for (int u : reverse_topological_order) {
for (auto : sam.st.trans) {
dp += dp;
}
}
}
string kth_substring(SAM &sam, int k) {
string res;
int u = 0;
while (k > 0) {
for (auto : sam.st.trans) {
if (k > dp) k -= dp;
else {
res.push_back(c);
u = v;
k--;
break;
}
}
}
return res;
}复杂度：预处理 O(n)，查询 O(|ans|)。
总结表
应用场景核心方法时间复杂度子串存在性检查SAM 上转移匹配\(O(|P|)\)不同子串计数利用 len - len]\(O(n)\)子串出现次数Parent 树 DFS 统计 cnt预处理 \(O(n)\)最长重复子串找 cnt ≥ 2 的最深状态\(O(n)\)多字符串 LCS广义 SAM + 状态覆盖统计\(O(\sum |S_i|)\)字典序第 k 小子串DAG 上 DP + 字典序 DFS预处理 \(O(n)\)恭喜你，现在你是真的学完SAM啦
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]