后缀自动机能在线性时间内构建并解决子串相关问题，其核心是通过状态转移和后缀链接表示所有子串。
后缀自动机（Suffix Automaton，简称 SAM）是处理字符串子串问题的高效数据结构。它能在 O(n) 时间内构建，并支持快速解决子串计数、最长公共子串、不同子串个数等问题。下面介绍 C++ 中如何实现一个基础的后缀自动机。
什么是后缀自动机
后缀自动机是一个有向图，其中每个节点代表原字符串某个子串的“状态”，边表示在该状态后添加一个字符能转移到的新状态。SAM 的核心性质包括：
所有从初始状态可达的路径，对应原串的所有子串。总状态数不超过 2n，转移边数不超过 3n。每个状态记录了该状态所代表子串的最长长度（len）和最小长度（通过 link 树推导）。
核心结构与变量定义
我们用结构体维护 SAM 的每个节点，主要包含以下字段：
len：当前状态能表示的最长子串长度。link：后缀链接（suffix link），指向另一个状态，表示当前状态的最长串的真后缀中最长的可接受状态。next[26]：转移数组，记录添加字符 a~z 后的下一个状态。
// 假设只处理小写字母struct State {int len; // 最长子串长度int link; // 后缀链接int next[26]; // 转移边State() {len = 0;link = -1;for (int i = 0; i
全局维护一个状态数组和相关变量：
立即学习“C++免费学习笔记（深入）”；
vector st;int last = 0; // 当前最后一个字符所在的状态int sz = 0; // 状态总数
构建后缀自动机
每次添加一个字符时，创建新状态并更新后缀链接。算法核心步骤如下：
void sam_init() {st.push_back(State());sz++;last = 0;}
void sam_extend(char c) {int cur = sz++;st.push_back(State());st[cur].len = st[last].len + 1;int p = last;
// 从 last 开始，沿着后缀链接走，直到根或已有 c 转移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.push_back(st[q]); // 复制 q 的信息 st[clone].len = st[p].len + 1; // 将 q 的转移复制，但不改变 len 和 link 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;
}
说明：
每次扩展字符 c，新建状态 cur，其最长长度为 last.len + 1。从 last 沿着 link 往上跳，为没有 c 转移的状态添加指向 cur 的边。若遇到已有 c 转移的状态 p，则检查目标状态 q 是否满足 len 条件。若不满足（即 q 是被多个路径共享的复杂状态），则需分裂出一个 clone 状态来保证正确性。
常见应用示例
利用 SAM 可以高效求解多种问题：
1. 不同子串个数
每个状态表示若干长度连续的子串，数量为 len – len(link)。累加所有状态即可。
long long count_distinct_substrings() { long long total = 0; for (int i = 1; i
2. 最短未出现子串
从初始状态开始 BFS，找第一个缺失的字符转移，该字符即是最短未出现子串。
3. 最长公共子串（两个串）
对第一个串建 SAM，然后用第二个串在 SAM 上匹配，维护当前匹配长度和状态，不断沿 link 跳转以缩短匹配。
int longest_common_substring(string s, string t) {int res = 0, v = 0, l = 0;for (char c : t) {while (v && st[v].next[c-‘a’] == -1) {v = st[v].link;l = st[v].len;}if (st[v].next[c-‘a’] != -1) {v = st[v].next[c-‘a’];l++;}res = max(res, l);}return res;}
基本上就这些。SAM 虽初看复杂，但掌握 extend 过程和 link 作用后，理解会清晰很多。关键是理解 clone 操作的意义：保持 DAG 中每个状态的 right 集合一致。
以上就是C++怎么实现一个后缀自动机(SAM)_C++高级字符串算法与子串问题的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1488541.html
微信扫一扫 
支付宝扫一扫 
