c++kquote>后缀自动机SAM是高效处理字符串子串问题的数据结构，能在O(n)时间内构建，支持查询子串出现次数、最长公共子串和不同子串个数；其核心由状态节点、转移边、后缀链接组成，通过扩展字符并维护len与link实现，关键步骤包括新建状态、沿后缀链接跳转、判断是否分裂状态以保证最小性；C++实现使用vector存储状态，map处理转移，常见应用有DP统计不同子串总数、反向传播计算出现频率、在SAM上匹配求两串最长公共子串等。
后缀自动机（Suffix Automaton, SAM）是一种高效处理字符串子串问题的数据结构。它能在 O(n) 时间内构建，并支持快速查询所有子串的出现次数、最长公共子串、不同子串个数等问题。C++ 实现 SAM 的核心是理解其状态转移机制和后缀链接（suffix link）。
什么是后缀自动机
SAM 是一个最小化确定性有限自动机，能识别字符串的所有后缀对应的子串。每个状态代表一组具有相同“右端行为”的子串集合。关键组成部分包括：
状态节点：包含 len（该状态表示的最长子串长度）、link（后缀链接指向更短的等价类）转移边 trans[c]：字符 c 的转移函数last：当前添加字符后的最新状态
构建后缀自动机的步骤
每次向字符串末尾添加一个字符时，扩展自动机结构。主要逻辑如下：
新建状态 cur，设置其 len 为 last->len + 1从 last 开始沿后缀链接向上跳，若没有 c 转移，则指向 cur遇到已有 c 转移的节点 p，设 q = p->trans[c]根据 len[q] 是否等于 len[p]+1 分裂状态或直接连接后缀链接
注意：分裂状态是为了保证 SAM 的最小性和正确性。
立即学习“C++免费学习笔记（深入）”；
C++ 实现代码
以下是简洁可运行的 SAM 实现：
“`cpp#include using namespace std;
struct State {int len, link;map trans;long long cnt; // 表示到达该状态的路径数（可用于统计子串数量）State() : len(0), link(-1), cnt(0) {}};
vector st;int last = 0;
void sam_init() {st.clear();st.push_back(State());last = 0;}
void sam_extend(char c) {int cur = st.size();st.push_back(State());st[cur].len = st[last].len + 1;int p = last;
while (p != -1 && !st[p].trans.count(c)) { st[p].trans[c] = cur; p = st[p].link;}if (p == -1) { st[cur].link = 0;} else { int q = st[p].trans[c]; if (st[p].len + 1 == st[q].len) { st[cur].link = q; } else { int clone = st.size(); st.push_back(st[q]); // 复制 q 状态 st[clone].len = st[p].len + 1; while (p != -1 && st[p].trans[c] == q) { st[p].trans[c] = clone; p = st[p].link; } st[q].link = clone; st[cur].link = clone; }}last = cur;
}
常见应用与操作
SAM 构建完成后可以解决多种问题：
- 不同子串个数：从初始状态出发，每条路径对应唯一子串。可用 DP 计算：f[u] = 1 + Σ f[v]（v 是 u 的转移目标）
- 每个子串出现次数：对每个状态标记是否为终止状态（出现在原串结尾），然后沿后缀链接反向传播计数
- 最长公共子串（两个串）：在 SAM 上匹配第二个串，维护当前匹配长度和状态，不断通过后缀链接调整
例如统计不同子串总数：
```cpplong long count_distinct_substrings() { long long total = 0; for (int i = 1; i < st.size(); i++) { total += st[i].len - st[st[i].link].len; } return total;}基本上就这些。掌握 SAM 关键在于理解状态含义和分裂条件。实现时注意 map 可换成数组（仅限小字符集），提升性能。
以上就是C++怎么实现一个后缀自动机(SAM)_C++处理所有子串问题的强大字符串数据结构的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1487952.html
微信扫一扫 
支付宝扫一扫 
