题目
给定字符串 s，在线构造 Suffix Automaton（SAM）。实现 extend(c)，说明每个状态的 len、link、转移和 endpos 含义，并用它计算不同子串数量、模式出现次数或最长公共子串。要求解释为什么状态数是 O(n)，以及何时必须创建 clone。
面试官考察点
- 能否把一个状态解释为一组具有相同
endpos的子串，而不是把它当作普通 Trie 节点。 - 能否正确区分连续转移、直接挂接和 clone 三种构造分支。
- 能否维护
len[link[v]] < len[v]、转移确定性和 suffix-link 树不变量。 - 能否把结构性质转化为计数、匹配和复杂度结论。
参考答案
SAM 是识别原串所有子串的最小部分 DFA。状态 v 保存该等价类中最长子串长度 len[v]，link[v] 指向最长的、属于另一个等价类的后缀。状态代表的长度区间是 (len[link[v]], len[v]]，因此一个状态可以覆盖多个不同长度的子串。
追加字符时先创建 cur，沿 suffix link 向后寻找缺少该转移的状态并补边。若遇到已有状态 q 且 len[p]+1 == len[q]，直接令 link[cur]=q；若不相等，复制 q 的转移创建 clone，把 clone 的 len 设为 len[p]+1，再沿 suffix link 把指向 q 的相关边改到 clone，并令 link[q] 与 link[cur] 都指向 clone。clone 保证每个状态的长度区间连续。
所有非根状态对不同子串的贡献是 len[v] - len[link[v]]。若先给原串前缀对应状态计数 1，再按 len 降序把计数累加到 link，即可得到每个等价类的出现次数。
实现示例
下面的伪代码展示核心构造；转移可以用哈希表或有序映射。
extend(c):
cur = new state
len[cur] = len[last] + 1
p = last
while p != -1 and c not in next[p]:
next[p][c] = cur
p = link[p]
if p == -1:
link[cur] = root
else:
q = next[p][c]
if len[p] + 1 == len[q]:
link[cur] = q
else:
clone = copy(q)
len[clone] = len[p] + 1
while p != -1 and next[p][c] == q:
next[p][c] = clone
p = link[p]
link[q] = link[cur] = clone
last = cur计算不同子串数量时遍历非根状态累加 len[v] - len[link[v]]。计算模式出现次数时沿转移走到对应状态，再读取按长度降序传播后的计数。
常见误区
- 把 SAM 当成只接受后缀的普通 Trie，忽略它实际压缩了所有子串的
endpos等价类。 - clone 复制了转移却忘记复制或重新设置
link，导致后续长度区间断裂。 - 修改转移时没有沿 suffix link 回溯到第一个不再指向
q的状态。 - 给 clone 计入一次前缀出现次数，造成所有出现次数偏大。
- 用固定数组存储巨大字符集，却没有说明空间成本和字符编码边界。
复杂度取舍
在固定字母表或哈希转移下，构造时间和空间为 O(n)，状态最多约 2n-1。若每个状态的转移使用平衡树，复杂度会增加到与字母表操作相关的对数因子。SAM 适合固定文本上的大量子串查询；需要字典序遍历、LCP 或后缀排序时，后缀数组可能更易控制内存和访问局部性。
SAM 的线性上界依赖在线追加模型。若要在字符串中间插入、删除或双端更新，通常需要不同结构，不能直接沿用 extend 的不变量。
先用空串、单字符、重复字符和触发 clone 的 abbb 做逐步断言，再随机生成字符串，与暴力集合比较不同子串数量和模式出现次数。最长公共子串测试可把第二个字符串逐字符送入 SAM，并在失配时沿 suffix link 回退。
参考资料
- CP-algorithms 的 SAM 讲义：状态区间、clone 构造和查询公式。
- Blumer 等人的最小子串自动机论文：状态与转移上界的理论来源。
- Carnegie Mellon 字符串算法讲义：后缀数组与后缀自动机的适用场景比较。
追问
为什么每个状态代表连续长度区间？
同一 endpos 等价类中的子串按长度排列时不会出现空洞；最长子串的后缀会逐步落入包含它的更大等价类。link 指向区间左侧的边界，因此区间正好是 (len[link[v]], len[v]]。
什么时候必须创建 clone？
当已有转移目标 q 的 len[q] 大于 len[p]+1 时，q 同时承载了两个不连续的长度范围。复制转移并把边界拆出 clone，才能恢复连续区间不变量。
为什么不同子串数量是这些区间长度之和？
每个状态覆盖的长度区间不重叠，且区间中的每个长度对应一个不同子串。把每个状态的区间大小相加，就得到全部非空不同子串数。
SAM 与 Aho–Corasick 如何选择？
SAM 面向一个文本的全部子串结构和多种统计；Aho–Corasick 面向一组已知模式在文本中的批量匹配。需求是模式集合固定还是文本结构固定，决定了构造方向。
如何扩展到最长公共子串？
先为字符串 S 建 SAM，再扫描 T。沿转移前进并维护当前匹配长度；失配时沿 suffix link 回退并继续尝试，记录过程中出现的最大长度即可。