后缀自动机（sam）是为单个主串s构建的o(n)时空紧凑结构，用于高效查询所有子串性质，如不同子串数、出现次数、位置及最长公共子串等，而非直接匹配模式串。

后缀自动机（Suffix Automaton，SAM）不是用来“匹配某个模式串”的传统工具，而是为**单个主串 S 构建一个紧凑结构，支持高效查询其所有子串的各类性质**。它不直接替代 KMP 或 AC 自动机做“文本中找模式”的动作，但能以 O(n) 时间与空间预处理 S 后，快速回答诸如“S 中有多少个不同子串”“子串 t 在 S 中出现多少次”“t 的所有出现位置”“最长公共子串”等复杂问题。

核心实现逻辑：状态与转移

SAM 本质是一个有向无环图（DAG），每个节点代表一组 endpos 等价的子串（即在 S 中结尾位置集合相同的子串），边表示字符扩展。关键不在“存字符”，而在“建状态关系”：

• 每个状态包含：len（该状态能表示的最长子串长度）、link（后缀链接，指向其最长真后缀所在状态）、next[c]（字符 c 的转移边）
• 初始状态（root）对应空串，len=0；新字符 c 每次插入时，新建状态 cur，并沿 last 的 link 链向上跳，对未定义 next[c] 的状态补边
• link 构建分两种情况：若跳到的状态 p 的 next[c] 指向 q 且 len[q] == len[p]+1，则 cur→link = q；否则需拆点复制 q 并重连

解决匹配类问题的关键路径

SAM 本身不执行“从左到右扫描文本”的匹配过程，但它让以下查询变得极快：

deep-java-review

Java项目代码review工具。分析Git变更+完整调用链路上下文，推断业务需求，进行多维度评分和分类汇总，生成完整PRD文档。包含细粒度Java代码审查清单（Null安全、异常处理、Streams、并发、equals/hashCode、资源管理、API设计、性能、MyBatis/ORM、事务边界、SQL/DD...

下载

• 判断子串是否存在：从 root 出发，按子串 t 的每个字符走 next 边；若某步无转移，说明 t 不是 S 的子串
• 统计子串出现次数：每个状态维护 size（该状态对应子串在 S 中的出现频次），通过拓扑序自底向上合并 link 树子树 size 得到（叶子状态 size=1，其余 size = Σ 子树 size）
• 定位所有出现位置：需额外记录每个状态的 endpos 集合最小/最大值，或使用线段树合并；实际中常只维护 rightmost（最右出现位置）或 firstpos（首次出现起始位置）已够多数场景

对比其他自动机的适用边界

别把 SAM 当成万能匹配器——选错工具反而增加复杂度：

• 单模式匹配（如“在大日志里找 error”）→ 用 KMP，O(|S|+|T|)，代码短、易调试
• 多模式匹配（如“同时找 apple、banana、cherry”）→ 用 AC 自动机，一次建图、一次扫描，O(|S|+Σ|Pᵢ|+occ)
• 需动态分析主串 S 的子串全局性质（如“最长重复子串”“不同子串数”“两个字符串最长公共子串”）→ SAM 是最优解，O(|S|) 建图 + O(|query|) 查询

典型应用代码骨架（C++ 关键片段）

建 SAM 后，常见查询可直接调用：

• 不同子串总数 = Σ (st[i].len − st[st[i].link].len)，i 从 1 到 last
• 子串 t 是否存在：bool ok = true; int p = 0; for (char c : t) { if (!st[p].next[c-'a']) { ok = false; break; } p = st[p].next[c-'a']; }
• 子串 t 出现次数：先走到对应状态 p，答案就是 st[p].size（前提是已按拓扑序计算过 size）