后缀自动机 SAM

定义 SAM 是 DFA 确定性有限状态自动机,是一张 DAG 有向无环图。结点为 状态 ,边被为状态间的 转移。 图存在一个虚拟结点 SSS ,称作 初始状态 ,其它各结点均可从 SSS 出发到达。 每个 转移 都标有一些字母。从一个结点出发的所有转移均 不同 。从一个状态出发的转移标有的字母不同。 存在一个或多个 终止状态 。如果从初始状态 SSS 出发,最终转移到了一个终止状态,则路径上的所有转移连接起来一定是字符串 sss 的一个后缀。反之 sss 的每数个后缀均可用一条从 SSS 到某个终止状态的路径构成。 SAM 包含关于字符串 sss 的所有子串的信息。如果从初始状态 SSS 出