2026 年省选专题系列四：后缀自动机 SAM。
SAM 是什么
后缀自动机是一个能识别字符串所有子串的自动机，节点数 O(2n)。
SAM 的核心概念
- 状态：代表一个等价类
- 转移：字符转移
- parent 树：状态之间的父子关系
- endpos：状态出现的结束位置集合
SAM 的构造
在线构造，每次加入一个字符，O(n) 复杂度。
经典应用
- 求不同子串个数
- 求最长公共子串
- 求字典序第 k 小子串
- 求出现次数
- 求多个串的公共子串
学习建议
- 先掌握 SAM 的构造
- 理解 parent 树
- 多做应用题
省选一对一辅导：151 6522 2880