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 中结束位置集合 (endpos) 完全相同」的子串归为一个状态——于是 $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(t) = 它在 s 中所有出现的结束位置的集合。把 endpos 完全相同的子串归为一类——这就是一个状态。关键事实：同一类里的子串，必然是长度连续的一串、且彼此为后缀关系。于是一个状态用两个数就能刻画它代表的那一组子串：len = 类中最长子串的长度，link = 指向的"上一类"（去掉最长子串的首字符后掉进的更大的类），该状态代表的子串长度恰好落在 (len[link], len]。点任意状态看它到底装着哪几个子串。

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

link 指向"少一截"。沿一个状态的 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 的副本 clone，复制 q 的出边与 link，再把指向 q 的那些边改指 clone。这就是整段算法唯一的难点。默认串 abcbc 会触发一次 clone。

实线 = transition（读一个字符走一步，标签是字符）；虚线 = suffix link（指向"少一截"的等价类）。跟着配色看四个指针：cur（新建，玫红）、p（上爬指针，黄）、q（撞上的旧状态，粉）、clone（克隆体，橙）。

为什么是线性的？新建状态总数 ≤ 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 自己只保留"较长"的那部分。

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

suffix link tree · parent tree · len 区间

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

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

它就是反串的后缀树。s 的 suffix link 树，与 reverse(s) 的 suffix tree（压缩后缀 trie）在结构上一一对应：SAM 的 link 边 = 后缀树的边，len 区间 = 后缀树边上压缩掉的那段。suffix automaton / suffix tree / suffix array 三者本是同一份后缀信息的不同切面。

这棵树撑起所有计数类应用。本质不同子串数 = Σ 区间长度；子串出现次数 = 子树 endpos 大小；不同应用只是换一种方式遍历它。具体怎么落地见下文应用。状态本身代表什么、为什么这样分类，见 endpos 等价类。

4 · 应用：计数、定位与多串最长公共子串

distinct substrings · occurrences · LCS

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

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

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

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

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

与后缀树 / 后缀数组同源。一个串的 SAM 的 suffix link 树，正是其反串的 suffix tree（压缩后缀 trie）；三者 (suffix automaton / suffix tree / suffix array) 表达的是同一份后缀信息的不同切面，可互相转化。

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