后缀自动机

前言

SAM 全称后缀自动机，在 NOI 大纲里标记为 10 级算法，但并不是那么难，也算是本人学习的第一个 10 级算法。

记号与约定

字符串为 \(S\)，\(\lvert S \rvert\) 表示 \(S\) 的长度。

SAM 的建立

简单来说，SAM（当前的定义）有以下特征：

• 是一张 DAG，每条边表示一个字符。
• 存在一个初始节点 \(P\)。
• 存在若干个终止节点 \(T_i\)。
• 对于任意的 \(T_i\)，在 \(P\) 到 \(T_i\) 的路径上的所有字符组成的字符串是 \(S\) 的一个后缀。

例如，对于字符串 \(\texttt{pkxpxp}\)