AC 自动机复习

摘要

粗略地，对字符串集合（也叫模板串)$s_1,\ldots,s_k$定义 SAM$(Q,\Sigma,\delta, q_0)$：

• $Q$是状态集合：$s_i$的前缀的集合。
• $\Sigma$是字符集。
• $\delta:Q\times \Sigma \to Q$是转移函数：对于$q\in Q,c\in \Sigma$，$\delta(q,c)$表示在状态$q$的末尾添加字符$c$，并且删除长度最短的$q$的前缀到达的状态。
• $q_0$（$q_0\in Q$）是初始状态：$\varnothing$。

OI 界实现的 AC 自动机通常是没有终止状态的。

在常见的代码实现过程中，会记录额外的信息：

• $\theta: Q\to Q$，对于$q\in Q$，$\theta(q)$表示$q$的最近长后缀且与$q$出现次数不同，对应的状态。