后缀自动机 | Codeboy's Blog

形式陈述

转移图与接受语言

给定长度为 $n$ 的词 $s$ ，令

\operatorname{Suff}(s)=\{s[i..n):0\le i\le n\},

包括空后缀。后缀自动机（suffix automaton，SAM）是识别这一后缀语言的最小确定部分自动机：没有对应转移就拒绝。相对于总转移 DFA，它省略了空残余的拒绝陷阱态；补回该态即可得到最小完整 DFA。

同一转移图也支持子串查询。每个子串都是某个后缀的前缀，因此从初态能完整读出 $x$ ，当且仅当 $x$ 是 $s$ 的子串。把所有非陷阱状态设为接受态，就识别全部子串语言 $\operatorname{Fact}(s)$ ，包括空串；但改变接受集合后，这张图未必仍然最小。下面固定通常的 endpos 状态图，再分别说明两种接受规则。

endpos 类与后缀链接

对非空子串 $x$ ，令 $\operatorname{endpos}_s(x)$ 为它在 $s$ 中所有出现的末字符下标集合，采用 $0,\ldots,n-1$ 编号。非初态对应等价关系

x\sim_{\mathrm{end}}y \quad\Longleftrightarrow\quad \operatorname{endpos}_s(x)=\operatorname{endpos}_s(y)

的各个类。初态单独对应空前缀。每个状态 $v$ 保存该类最长子串长度 $\operatorname{len}(v)$ 、字符转移，以及后缀链接 $\operatorname{link}(v)$ ：它指向最长代表的真后缀中，不属于当前 endpos 类的最长者所在状态；没有非空候选就指向初态。初态长度为零，其链接用缺省标记表示。

同一类的短串必为长串的后缀：取长串的一次出现，两者在同一位置结束。夹在两者之间的后缀，其 endpos 又夹在相同的两个集合之间，因此也属于该类。由此，一个非初态恰包含最长代表在以下各长度上的后缀，每个长度一个：

\operatorname{len}(\operatorname{link}(v))+1, \ldots,\operatorname{len}(v).

所以它贡献 $\operatorname{len}(v)-\operatorname{len}(\operatorname{link}(v))$ 个不同非空子串。链接必须离开当前类：对 $s=\texttt{ab}$ ，ab 与 b 共享 endpos $\{1\}$ ；若只写“最长真后缀所在状态”，便会错误地产生自链接。

为什么后缀识别器最小

相对于 $\operatorname{Suff}(s)$ ，一个非空子串 $x$ 的合法右续写集合是

x^{-1}\operatorname{Suff}(s) =\{s[e+1..n):e\in\operatorname{endpos}_s(x)\}.

不同结束位置留下的后缀长度不同，因此这个集合与 endpos 集合一一对应。相同 endpos 给出同一残余，不同 endpos 给出不同残余；初态还允许续写整个 $s$ ，与非初态区分。不是子串的输入没有任何合法续写，统一落入被省去的空残余。Myhill–Nerode 定理因而证明这张部分自动机对后缀语言最小。

某状态接受后缀，恰当且仅当它的 endpos 含 $n-1$ ；等价地，标记读完整个 $s$ 的状态 last，再沿后缀链接标记到初态。 $n=0$ 时只有接受空串的初态。

直觉

SAM 合并的是“在文本的哪些位置结束”，而不是任意两段看起来相似的字符串。末尾再加一个字符时，某些旧的 endpos 类需要分开：较短成员可能获得一次新出现，较长成员却没有。clone 用来记录这次结构分裂，不代表多读入了一个字符。

后缀语言的残余恰能区分这些结束位置，所以 endpos 给出最小后缀识别器。只问子串成员时，可以忽略终止标记而检查转移是否存在；这项便利来自同一图的路径结构，最小性仍须相对于选定语言判断。

ababa 的 endpos 状态图叠加字符转移与后缀链接，以是否存在完整路径回答子串查询 — 后缀自动机的转移与后缀链接；图示查询采用全部状态接受的子串约定

例子与边界

两种接受规则不共享最小性结论

在图中的 ababa 状态图里，读取 bab 能到状态 $4$ ，所以它是子串；读取 baa 时缺少转移，所以不是子串。若只识别后缀，接受态则是 $0,1,3,5$ ，分别对应空串及 last 的链接链；状态 $4$ 不接受，因为 bab 不是 ababa 的后缀。

再看 $s=\texttt{abbb}$ 。b 的 endpos 为 $\{1,2,3\}$ ，ab 的 endpos 为 $\{1\}$ ，它们在 SAM 中必须分属两态。但在全部子串语言中，两者都恰可续写 $\{\varepsilon,\texttt b,\texttt{bb}\}$ ，因此把全体状态设为接受后，这两态可以继续合并。这是“识别全部子串”与“最小子串识别器”不同的具体见证。

在线扩展与 clone

维护已经处理前缀的状态 last。读入字符 $c$ 时，新建 $cur$ ，令 $\operatorname{len}(cur)=\operatorname{len}(last)+1$ 。从 $last$ 沿链接向上，为尚无 $c$ 转移的状态补上指向 $cur$ 的边，直到越过初态或遇到已有转移 $p\xrightarrow c q$ 。

若没有遇到已有转移，令 $\operatorname{link}(cur)$ 为初态。
若 $\operatorname{len}(p)+1=\operatorname{len}(q)$ ，直接令 $\operatorname{link}(cur)=q$ 。
否则新建 $clone$ ，复制 $q$ 的出边与原后缀链接，令其长度为 $\operatorname{len}(p)+1$ 。从当前 $p$ 继续沿链接向上，把仍通过 $c$ 指向 $q$ 的边改指向 $clone$ ，直到遇到不同转移或越过初态；最后令 $q,cur$ 的链接都指向 $clone$ 。

随后令 $last=cur$ 。第三种情况把需要新长度边界的短成员分离出来，同时保留原来较长成员的后续转移。每次扩展至多新建一个普通状态和一个 clone；前两个字符不会触发 clone，所以 $n\ge2$ 时至多有 $2n-1$ 个非陷阱状态。 $n=1$ 时有两态，空串时有一态。

经典构造的转移总数也是 $O(n+1)$ ，但这需要独立的结构分析，不能仅由线性状态数推出。在常数字母表的单位成本模型中，在线构造总时间和空间均为 $O(n+1)$ ；稀疏有序字典一般会带上字符查找的对数因子。

子串计数与出现次数

不同非空子串数为

\sum_{v\ne\mathrm{root}} \bigl(\operatorname{len}(v)-\operatorname{len}(\operatorname{link}(v))\bigr).

对 ababa，各非初态贡献 $1,2,2,2,2$ ，共 $9$ 个。若要统计非空子串出现次数，给每次扩展新建的普通状态初值 $1$ 、clone 初值 $0$ ，再按 len 降序向链接父亲累加。这把每个真实末位置贡献给包含它的 endpos 类；clone 本身没有新增末位置，初值为 $1$ 会重复计数。空串的出现次数另按全部 $n+1$ 个边界处理。

若只按不同回文内容建索引，回文树采用另一种节点划分：一种回文一个节点，没有SAM的endpos等价类或clone。它也可沿后缀链接汇总出现次数，但扩展边表示两端同时加同一字符，不能当作本页自动机逐字符读取的转移。

推论与应用

SAM 支持子串成员查询、不同子串计数、出现次数与最长公共子串。按字典序查第 $k$ 个不同非空子串时，还需在转移 DAG 上计算每态向后可形成的路径数，再按有序字符跳过整块路径；endpos 出现次数与这项路径数是不同摘要。

后缀树按前缀共享压缩后缀，后缀数组与 FM-index 围绕后缀序建立静态索引。SAM 的 endpos 图不直接给出 suffix-array 区间、位置列表或文本提取；这些查询需要另加信息与相应的时间、空间分析。

参考资料

Jean Berstel, Luc Boasson, Olivier Carton and Isabelle Fagnot, Minimization of Automata, 2010，§9.1：后缀自动机的最小后缀语言定义与线性规模；§2：残余语言与最小性。
Maxime Crochemore and Wojciech Rytter, Jewels of Stringology, World Scientific, 2002, Chapter 5.
Anselm Blumer et al., “The Smallest Automaton Recognizing the Subwords of a Text,” Theoretical Computer Science 40, 1985, pp. 31–55：最小子串识别器这一相关但不同的对象。

形式陈述 ​

转移图与接受语言 ​

endpos 类与后缀链接 ​

为什么后缀识别器最小 ​

两种接受规则不共享最小性结论 ​

在线扩展与 clone ​

子串计数与出现次数 ​