后缀自动机 | Codeboy's Blog

形式陈述

给定长度为 $n$ 的词 $s$ ，记其全部连续子串组成的语言为

\operatorname{Fact}(s)=\{x:x\text{ 是 }s\text{ 的连续子串}\}.

后缀自动机（suffix automaton, SAM）可定义为识别 $\operatorname{Fact}(s)$ 的最小确定有限自动机的部分转移版本：从初态沿字符转移能读完整个 $x$ ，当且仅当 $x\in\operatorname{Fact}(s)$ ；所有可达非陷阱状态都接受，缺失转移表示拒绝。若要求总 DFA，可补一个拒绝陷阱状态，此时状态数相应增加一。

非初态对应由等价关系划分出的子串 $endpos$ 类：

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

其中 $\operatorname{endpos}_s(x)$ 是 $x$ 在 $s$ 中所有出现的结束位置集合。每个状态 $v$ 记录：

$\operatorname{len}(v)$ ：该类中最长子串长度；
$\operatorname{link}(v)$ ：最长子串的最长真后缀所在状态；
按字符标记的确定转移。

该状态代表长度区间

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

中的若干子串，共贡献

\operatorname{len}(v)-\operatorname{len}(\operatorname{link}(v))

个不同子串。

在线构造逐字符扩展当前最长前缀。若新增转移会让某状态同时承担不相容的长度结构，就克隆该状态：复制转移与 suffix link，调整 len，并重定向相关转移。长度 $n\ge2$ 的字符串至多有 $2n-1$ 个非陷阱状态； $n=1$ 时有初态与一个字符状态。转移总数为 $O(n)$ （固定有限字母表或显式稀疏转移表示）。

直觉

SAM 把“拥有相同未来出现位置”的子串合并。状态不是某一个字符串，而是一个等价类；因此 clone 不是复制一次真实出现，而是把原先合并过度的类按未来行为拆开。

名称中的“后缀”来自在线构造与 suffix link，不表示自动机只接受后缀。默认把所有可达状态设为接受时，它识别全部子串。若只把最终状态 last 及其 suffix-link 链上的状态标为接受，则同一转移图可识别 $s$ 的后缀语言。两种接受约定必须明确区分。

ababa 的后缀自动机在同一状态图上叠加字符转移与后缀链接，并标出成功和失败查询 — 后缀自动机的转移与后缀链接

例子与边界

对 ababa，沿转移读取 bab 成功，因此它是子串；读取 baa 时缺失转移，因此拒绝。不同子串数为

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

要统计出现次数，可令每个新建非 clone 状态初值为 $1$ 、clone 初值为 $0$ ，再按 len 降序把计数累加到 suffix link。clone 不代表新结束位置，给它初值 $1$ 会系统性高估频次。

最小性是相对于指定语言与自动机约定的。把缺失转移补成显式 sink，会比常见 SAM 实现多一个状态；把接受状态改成后缀集合，语言也从所有子串变为所有后缀。不能一边使用 partial-DFA 状态界，一边又暗中计入 sink。

推论与应用

SAM 可在线支持子串成员查询、不同子串计数、出现次数、最长公共子串和字典序第 $k$ 个不同子串。后一任务需在转移 DAG 上计算每个状态之后可形成的路径数，并按字符顺序跳过整块路径；endpos 出现次数不是路径数。

后缀树按前缀共享压缩后缀，后缀数组与 FM-index 围绕后缀序和 BWT 建立静态索引。SAM 按右上下文合并子串，不直接提供 suffix-array interval、locate 或文本提取接口；这些结构共享字符串对象，却保留不同信息。

参考资料

Anselm Blumer et al., “The Smallest Automaton Recognizing the Subwords of a Text,” Theoretical Computer Science 40, 1985, 31–55.
Maxime Crochemore and Wojciech Rytter, Jewels of Stringology, World Scientific, 2002, Chapter 5.
Mehryar Mohri, “Finite-State Transducers in Language and Speech Processing,” Computational Linguistics 23(2), 1997, §2.
OI-Wiki contributors, Suffix Automaton, OI-Wiki, accessed 2026.

形式陈述 ​

反向链接

形式陈述