形式陈述

后缀自动机的状态对应子串按右端位置集合 $endpos$ 的等价类。每个状态记录该类中子串的最大长度 len，后缀链接指向严格更大的后缀等价类。 逐字符扩展时创建新末状态；若现有转移的长度关系不满足，需要克隆状态以拆分等价类。长度 $n$ 的字符串至多产生 $2n-1$ 个状态与线性数量级转移。

直觉

许多不同子串拥有完全相同的后续出现位置，把它们合并为一个状态即可压缩所有子串。

例子与边界

沿转移可判断某串是否为子串；状态贡献 len[v]-len[link[v]] 个不同子串。后缀自动机不是后缀 Trie，也不直接保留每个出现位置，克隆状态尤其容易实现错误。

推论与应用

用于不同子串计数、最长公共子串、出现次数统计和字符串上的路径动态规划。

参考资料

• OI-Wiki contributors, OI-Wiki (2026), suffix automaton.
• cp-algorithms contributors, Algorithms for Competitive Programming (2026), suffix automaton.