后缀自动机（Suffix Automaton）详解：原理、构建与应用

1. 什么是后缀自动机后缀自动机Suffix Automaton简称 SAM是一种用于处理字符串的有限状态自动机。它能够接受给定字符串S的所有后缀并且是满足这一性质的最小确定性有限状态自动机。后缀自动机在字符串匹配、子串计数、最长公共子串等问题中有着广泛的应用。2. 核心概念与性质2.1 状态与转移后缀自动机由一组状态节点和转移边构成。每个状态代表字符串S的某个等价类该类中的所有子串具有相同的结束位置集合即 right 集合。转移边表示在当前字符串后添加一个字符所能到达的新状态。2.2 后缀链接Link每个状态都有一个后缀链接suffix link指向一个状态该状态所代表的子串是当前状态所代表子串的最长真后缀。后缀链接构成了一个树形结构称为后缀链接树Link Tree。2.3 关键性质状态数对于长度为n的字符串后缀自动机的状态数不超过2n-1。转移数转移边的数量不超过3n-4。线性构建可以在O(n)时间内在线构建后缀自动机。3. 构建算法增量法后缀自动机通常采用增量法在线构建每次向当前字符串末尾添加一个字符c。以下是构建过程的伪代码描述struct State { int len, link; mapchar, int next; }; vectorState st; int last, sz; void sa_init() { st.resize(1); st[0].len 0; st[0].link -1; last 0; sz 1; } void sa_extend(char c) { int cur sz; st.push_back(State()); st[cur].len st[last].len 1; int p last; while (p ! -1 !st[p].next.count(c)) { st[p].next[c] cur; p st[p].link; } if (p -1) { st[cur].link 0; } else { int q st[p].next[c]; if (st[p].len 1 st[q].len) { st[cur].link q; } else { int clone sz; st.push_back(st[q]); st[clone].len st[p].len 1; while (p ! -1 st[p].next[c] q) { st[p].next[c] clone; p st[p].link; } st[q].link st[cur].link clone; } } last cur; }4. 应用场景4.1 不同子串个数利用后缀自动机可以高效计算字符串中不同子串的数量。每个状态v所代表的子串数量为st[v].len - st[st[v].link].len对所有状态求和即可。4.2 最长公共子串LCS对于两个字符串S和T可以构建S的后缀自动机然后用T在自动机上匹配维护当前匹配长度即可在O(|T|)时间内求出最长公共子串。4.3 子串出现次数通过预处理每个状态的 right 集合大小即 endpos 大小可以快速查询任意子串在原串中的出现次数。4.4 字典序第 k 小子串在后缀自动机上 DP 求出每个状态出发能到达的子串数量然后按字典序遍历即可找到第 k 小的子串。5. 代码示例C 实现以下是一个完整的后缀自动机实现包含构建和不同子串个数计算#include iostream #include vector #include map #include string using namespace std; struct SuffixAutomaton { struct State { int len, link; mapchar, int next; }; vectorState st; int last, sz; SuffixAutomaton() { st.resize(1); st[0].len 0; st[0].link -1; last 0; sz 1; } void extend(char c) { int cur sz; st.push_back(State()); st[cur].len st[last].len 1; int p last; while (p ! -1 !st[p].next.count(c)) { st[p].next[c] cur; p st[p].link; } if (p -1) { st[cur].link 0; } else { int q st[p].next[c]; if (st[p].len 1 st[q].len) { st[cur].link q; } else { int clone sz; st.push_back(st[q]); st[clone].len st[p].len 1; while (p ! -1 st[p].next[c] q) { st[p].next[c] clone; p st[p].link; } st[q].link st[cur].link clone; } } last cur; } long long countDistinctSubstrings() { long long ans 0; for (int i 1; i sz; i) { ans st[i].len - st[st[i].link].len; } return ans; } }; int main() { string s ababa; SuffixAutomaton sam; for (char c : s) sam.extend(c); cout 不同子串个数: sam.countDistinctSubstrings() endl; return 0; }6. 总结后缀自动机是一种功能强大且高效的字符串数据结构它在线性时间内构建并支持多种字符串查询操作。虽然其原理和构建算法较为复杂但一旦掌握便能解决许多经典的字符串难题。建议读者通过动手实现代码和解决实际问题来加深理解。