第 5 章 · 03 SAM 后缀自动机难点精讲 ★

第 5 章 · 03 SAM 后缀自动机难点精讲 ★

本节定位：对应 OI Wiki docs/string/sam.md。难度：高阶（省选/IOI）。前置依赖：第 5 章 · 02 节字符串基础（尤其 KMP 的 fail 思想、Trie）、树形结构（parent tree 是棵树）。本节是难点精讲节（★），对 SAM 做 Wiki 之外的增量慢节奏讲解，作 docs/string/sam.md 的配套讲义，不重写 Wiki。

⚠️ 注意：SAM 被公认为"字符串算法的顶峰"。Wiki 页面写得已经很全，但概念密度极高。本节的任务是把这些概念拆开、排序、画图，让你先建立直觉再回 Wiki 看证明。

为什么难

SAM 之所以劝退，是多个抽象概念同时交织，没有任何一个可以单独跳过：

1. endpos 等价类：用"结束位置集合"给所有子串分类，这是 SAM 状态的定义来源。
2. parent tree（后缀链接树）：等价类之间有包含关系，构成一棵树，方向和深度极易搞混。
3. 转移函数 trans：状态 + 字符 → 状态，是一张 DFA（有限状态自动机）。
4. 在线构建算法：逐字符加入，维护 last 指针，分两种情况——其中 clone（克隆节点）是最难理解的一步。

这四者环环相扣：不懂 endpos 就不懂状态，不懂 parent tree 就不懂 link，不懂 link 就看不懂构建算法里的 clone。所以本节按"定义 → 概念1→2→3→4 → 构建算法 → 应用"的顺序逐层加概念。

慢节奏精讲（docs/string/sam.md）

定义：SAM 是什么

字符串 s 的 SAM 是一个能识别 s 所有子串的最小 DFA（确定性有限状态自动机）。

• 换句话说：从 SAM 的起点出发，任意一条路径上的字符拼起来，都是 s 的某个子串；s 的每个子串也都对应一条路径。
• "最小"指状态数最少——长度 n 的串，SAM 最多 2n-1 个状态、3n-4 条转移，空间 O(n)。
• 与"对所有后缀建 AC 自动机"对比：AC 自动机最坏 Θ(n²) 个节点，SAM 把重复节点合并到 O(n)。从这个意义上，SAM 是后缀的"压缩 AC 自动机"。

核心概念 1：endpos（结束位置集合）

对子串 t，endpos(t) = t 在 s 中所有结束位置的集合（下标从 0）。

例：s = abcbc，则 endpos("bc") = {2, 4}（在第 2、4 位结束）。

关键观察：两个子串 endpos 相同 ⟺ 它们在 s 中"总是形影不离"地出现。

核心概念 2：endpos 等价类

按 endpos 是否相同，把 s 的所有子串分成若干等价类。

💡 关键事实：SAM 的每个状态 = 一个 endpos 等价类（再加一个初始状态）。这是 SAM 把 Θ(n²) 压到 O(n) 的根本原因——等价类个数是线性的。

引理（直觉版）：同一等价类里的子串，长度连续，且"长的包含短的"——它们互为后缀。

核心概念 3：parent tree（后缀链接 link）

不同等价类的 endpos 集合有包含关系：endpos 大的类，对应子串更短。把这些包含关系组织成一棵树，就是 parent tree。

• link(v)：状态 v 的后缀链接，指向"endpos 真包含 v 的那个最紧的等价类"。
• 沿 link 往上走，子串越来越短，endpos 越来越大。
• parent tree 的根是初始状态 t0（endpos 是所有位置）。

⚠️ 注意：parent tree 的方向是初学者最易搞混的点。记住口诀："沿 link 向上，串变短、endpos 变大；根在最上面，endpos 最大。" 别画反。

核心概念 4：转移 trans

每个状态 v 有一条 trans[v][c]：从 v 读入字符 c 后到达的状态。这张转移图就是 SAM 本体（一张 DAG）。

一个状态要维护三个东西：len（该类最长子串长度）、link（后缀链接）、trans（转移字典）。

★ 在线构建算法（逐字符加入）

维护 last = 当前整个已加入前缀所在的状态。每加入一个字符 c，分两种情况：

Case 1（简单情况）：新建状态 cur，len[cur] = len[last] + 1。从 last 沿 link 往上走，凡是没有 c 转移的，都把 trans 指向 cur；若走到根都没冲突，直接 link[cur] = t0。

Case 2（需要 clone，最难）：从 last 沿 link 往上走时，遇到一个状态 p 已有 c 转移到 q。这时要判断：

• 若 len[q] == len[p] + 1：直接 link[cur] = q，结束。
• 若 len[q] > len[p] + 1（q 还代表更长的串）：必须 clone——把 q 复制成 clone，len[clone] = len[p] + 1，继承 q 的 trans 和 link，然后让 q 和 cur 的 link 都指向 clone，再把 p 这条链上原本指向 q 的 c 转移改指向 clone。

💡 clone 为什么必须：q 原本"身兼两职"（既代表长串又代表短串），加入 cur 后这两种身份必须分开，否则转移会出错。clone 就是把"短串身份"剥离出来。这一步没有直觉捷径，只能对着 Wiki 的例子（如 aab、ababa）手推。

构造的总复杂度是 O(n)（字符集视为常数），这是 SAM 比后缀数组 SA"在线 + 线性"的优势所在。

应用

• 不同子串个数：每个状态贡献 len[v] - len[link[v]] 个新子串，求和即得。
• 最长公共子串（两串）：对一个串建 SAM，另一个串在上面跑，维护当前匹配长度。
• 第 k 小子串：在 SAM 的 DAG 上按字典序做"走 k 步"，先预处理每个状态后继路径数。

与后缀数组 SA 的对比

两者解决大量重叠的问题，但 SAM 在线构建、状态线性，更适合"动态加字符"的场景。

常见误区

1. 忘了 clone：写构建算法时漏掉 Case 2 的 clone 分支，构造出的 SAM 状态数会超线性、转移错误。务必把 len[q] > len[p] + 1 这个判断写全。
2. parent tree 方向画反：把 link 当成"父指向子"。记住 link 是"子 → 父"，根在顶部。
3. 混淆 len 和 minlen：状态 v 的子串长度范围是 [len[link[v]] + 1, len[v]]，不是只有 len[v] 一个。
4. 以为 SAM 和 AC 自动机无关：link 本质就是 AC 自动机 fail 指针在 SAM 里的对应，理解了 KMP/AC 的 fail，link 的直觉就有了。

练习建议

• P3804 【模板】后缀自动机（不同子串个数/子串出现次数）：建出 SAM 后在 parent tree 上做子树大小统计。先过模板题，确认构建算法无 bug。
• 进阶：最长公共子串（SPOJ LCS / 洛谷 P1812）、第 k小子串（洛谷 P3975）。
• 学法：先对着 Wiki 的图手推 aab、ababa 的构建全过程（每加一个字符画一张 SAM），再写代码。没有手推直接写，几乎必然调一晚上。

💡 学习提示：SAM 是"看懂证明 ≠ 会写代码"的典型。建议先抄一遍 Wiki 的模板代码 AC 模板题，再回头理解每个分支的作用，最后才尝试自己从零写。

本节要点

• SAM = 识别所有子串的最小 DFA，状态数 O(n)，构建 O(n)。
• 四个核心概念：endpos、等价类、parent tree（link）、trans。
• 构建算法逐字符加入，难点在 Case 2 的 clone（克隆节点分裂）。
• parent tree 方向：link 从子指向父，沿 link 向上串变短、endpos 变大。
• SAM 在线、SA 离线；练习从 P3804 模板题开始，务必手推小例子。