后缀自动机(SAM)

定义

后缀自动机(Suffix Automaton,SAM)是接受某字符串全部后缀(从而其路径覆盖全部子串)的最小确定性有限自动机。它由 Blumer 等人于 1980 年代提出,状态数不超过 2n-1,转移数不超过 3n-4。

原理

SAM 的每个状态对应一个 endpos 等价类,即一组在原串中结束位置集合相同的子串;状态之间由父指针(link)构成一棵后缀链接树(parent 树)。构造采用在线增量算法,每次追加一个字符,均摊 O(1),整体线性。

应用

利用 SAM 可以在线性或近线性时间解决:统计本质不同子串数量、求任意子串出现次数、最长公共子串、字典序第 k 小子串等问题;parent 树本身也常被当作树结构做进一步统计。

优缺点

优点是功能覆盖面广、构造在线且高效;缺点是概念抽象、正确实现门槛较高,多用于算法竞赛与专业字符串处理库。