endpos · sa_extend · suffix link 树

后缀自动机 · Suffix Automaton

一个串 $s$ 的 suffix automaton (SAM) 是识别 $s$ 全部子串的最小 DFA：从初始状态出发，沿 transition 读入任意一段字符，能走通当且仅当这段字符是 $s$ 的一个 substring。关键之处在于，尽管 $s$ 的不同子串可多达 $O(n^2)$ 个，这台机器只需不超过 $2n-1$ 个状态、 $O(n)$ 条边，而且能在线、线性地一字符一字符建出来。

它能做到这点，靠的是一个核心抽象：endpos 等价类。把「在 $s$ 中结束位置集合完全相同」的子串归为一个状态，于是 $O(n^2)$ 个子串被压进 $O(n)$ 个状态。每个状态再记两样东西：len（它代表的最长子串长度）和 link（suffix link，指向少一截的等价类）。这些 suffix link 自然连成一棵 parent 树，本质不同子串计数、子串出现次数、多串最长公共子串等问题，都化作在这台机器或这棵树上的一次遍历。

本页分四节贯通：endpos 等价类、在线增量构造、suffix link 树、三类应用。

1 · endpos 等价类：为什么状态这样定义

endpos · 等价类 · 子串识别

先看 SAM 怎么用：从初始状态 t0 出发，把一段字符逐个沿 transition 走下去，能走通这段字符就是 $s$ 的一个子串；中途某个字符没有出边，就不是。一台机器同时认出了 $s$ 的所有子串。子串可能有 $O(n^2)$ 个，机器却只有几个状态，秘密在于很多子串被合并进了同一个状态，合并的依据就是 endpos。

一个子串 $t$ 的 endpos 是它在 $s$ 中所有出现的结束位置的集合。把 endpos 完全相同的子串归为一类，这就是一个状态。关键事实：同一类里的子串必然是长度连续的一串、且彼此为后缀关系。于是一个状态用两个数就能刻画它代表的那一组子串：len 是类中最长子串的长度，link 指向上一类（去掉最长子串的首字符后掉进的更大的类），该状态代表的子串长度恰好落在 $(len[link],\ len]$ 。

图 1-1 · 状态与它装着的那几个子串。可点任意状态展开它代表的子串列表，也可换预设串。

建议 · 把「endpos 相同」当成一个等价关系来想，后面全都顺理成章：它把全部子串划成 $O(n)$ 个类，这正是状态数不超过 $2n-1$ 的根源。两个子串 endpos 相同，意味着它们在 $s$ 里总是结伴出现——哪里有这个，哪里就有那个，因此自动机不必区分它们，可共用一个状态与同一套后续 transition。

注 · 沿一个状态的 suffix link 走，等价于把它代表的最长子串不断砍掉最前面的字符；每砍到 endpos 集合变大（出现得更频繁）的那一刻，就跨入下一个状态。一路砍到空串，就回到了根 t0。这些 link 连起来是一棵树，见 suffix link 树一节。

2 · 在线增量构造：逐字符长出这台机器

online construction · sa_extend · clone

SAM 最漂亮的性质之一是在线构造：无需预先看到整个串，每读入一个字符调用一次 extend，就把机器扩成「已读前缀的 SAM」。维护一个 last 指向整段已读前缀对应的状态。每次 extend(c) 新建状态 cur，从 last 沿 suffix link 向上爬，给沿途还没有 c 出边的状态补一条指向 cur 的 transition。

爬的过程中一旦撞上已有 c 出边的状态（下称 p），就要决定 link[cur] 指向谁。设那条边通向 q：若 len[p] + 1 === len[q]（长度恰好连续），直接 link[cur] = q；否则 q 把长的和短的子串混在了一个状态里，必须 clone——拆出一个 len = len[p] + 1 的副本，复制 q 的出边与 link，再把指向 q 的那些边改指副本。这是整段算法唯一的难点。

图 2-1 · 逐字符建机。实线是 transition（标签为字符），虚线是 suffix link。跟着配色看四个指针：cur 新建（玫红）、p 上爬（黄）、q 撞上的旧状态（粉）、克隆体（橙）。默认串 abcbc 会走两次 clone 分支（克隆体 t5 与 t7），预设里的 aabb 则只有一次。

线性的来由值得单独确认一遍：新建状态总数不超过 $2n-1$ ；两个 while 循环的总步数用势能分析（跟踪 $len[last] - len[link[last]]$ 之类的量）可证为均摊 $O(1)$ 。于是整段构造是 $O(n)$ ，前提是字符集为常数。clone 的作用则是维持「一个状态等于一组 endpos 相同子串」这条不变量——endpos 等价类一节解释了为什么长短混装必须拆开。

警示 · clone 不是另起炉灶，而是沿用历史。克隆体复制 q 的全部出边与 suffix link，只把 len 调小到 len[p] + 1；随后 q 与 cur 的 link 都改挂到它。换句话说，clone 接管了 q 里较短的那部分子串，q 自己只保留较长的那部分。一次 extend 最多产生一个克隆体，但整串下来可以出现多个——abcbc 就有两个。

3 · Suffix link 树：被压进结构里的全部子串

suffix link tree · parent tree · len 区间

把 SAM 的 transition 全部隐去，只留 suffix link，它们恰好构成一棵以根 t0 为根的树，常称 parent 树。这棵树才是 SAM 真正存住信息的地方：每个状态 $v$ 代表长度落在 $(len[link[v]],\ len[v]]$ 区间的那几个子串，沿 link 往根走一步，就把当前最长子串砍掉最前面一个字符、掉进一个出现得更频繁的类。

两个推论立刻可用。其一，把每个状态的区间长度 $len[v] - len[link[v]]$ 全加起来，正好是 $s$ 的本质不同子串个数，因为每个子串被恰好一个状态、一个长度计到一次。其二，一个状态的 endpos，等于它在这棵树里整棵子树所有前缀叶子的并集——这让「出现次数」变成一次自底向上的子树求和。

图 3-1 · 只保留 suffix link 后的 parent 树。可点任意状态，看它到根的 link 链与它管辖的子串长度区间。

记住一句话就能把三种后缀结构串起来： $s$ 的 suffix link 树，与 $reverse(s)$ 的 suffix tree（压缩后缀 trie）在结构上一一对应——SAM 的 link 边就是后缀树的边，len 区间就是后缀树边上压缩掉的那段。suffix automaton、suffix tree、suffix array 三者本是同一份后缀信息的不同切面。

4 · 三类应用

distinct substrings · occurrences · LCS

一旦 $O(n)$ 把 SAM 建好，大量「子串集合」类问题都退化成在这台机器或它的 suffix link 树上的一次线性遍历。本节挑三个最常见的：本质不同子串个数、某模式的出现次数、两串的最长公共子串。

图 4-1 · 三类应用共用一台已建好的机器。可用上方下拉切换要演示的问题，并换输入串。

$\sum (len - len[link])$ 之所以就是答案，关键在互不相交：每个状态 $v$ 代表长度落在 $(len[link],\ len]$ 的那一组子串，不同状态代表的子串集合互不相交、并起来恰好是 $s$ 的全体不同子串。所以把每个状态贡献的区间长度加起来，就是本质不同子串总数，一次遍历 $O(n)$ 。

注 · 出现次数等于 endpos 大小，在 link 树上自底向上累加即可：构造时让每个前缀状态初始计数 1、clone 初始 0，再沿 suffix link 树把子树计数加到父亲，每个状态的最终计数就是它代表的子串的出现次数。最长公共子串则反过来——拿 $s$ 的 SAM 去读 $t$ ，匹配不动就沿 suffix link 缩短当前匹配长度，全程记录达到过的最大匹配。

5 · 后缀自动机出现在哪里

竞赛与文本处理中，SAM 是「子串集合」类问题的统一工具：本质不同子串计数与第 $k$ 大子串、子串出现次数与首末出现位置、多个串的最长公共子串、最小循环移位等，都能在 $O(n)$ 构造之上以一次线性遍历解决。

把构造推广到多个串（或一棵 trie），得到 generalized SAM，用于在一组文档里做子串检索与统计——这与全文索引、生物信息学里的序列比对思路相通。