后缀自动机 SAM

一句话理解

SAM 后缀自动机：接受所有后缀的最小 DFA。

为什么要学

状态是 endpos 集合。

讲解

功能极强：子串个数、本质不同子串。难写。

例子

每个状态代表一类子串。

常见错误

• 和 AC 自动机混淆。
• clone 节点漏更新。