AC自动机
解释
简单来说，建立一个 AC 自动机有两个步骤：
- 基础的 Trie 结构：将所有的模式串构成一棵 Trie。
- KMP 的思想：对 Trie 树上所有的结点构造失配指针。
然后就可以利用它进行多模式匹配了。
字典树构建
AC 自动机在初始时会将若干个模式串丢到一个 Trie 里，然后在 Trie 上建立 AC 自动机。这个 Trie 就是普通的 Trie，该怎么建怎么建。
这里需要仔细解释一下 Trie 的结点的含义，尽管这很小儿科，但在之后的理解中极其重要。Trie 中的结点表示的是某个模式串的前缀。我们在后文也将其称作状态。一个结点表示一个状态，Trie 的边就是状态的转移。
形式化地说，对于若干个模式串 ，将它们构建一棵字典树后的所有状态的集合记作 。
失配指针
AC 自动机利用一个 fail 指针来辅助多模式串的匹配。
状态 的 fail 指针指向另一个状态 ，其中 ，且 是 的最长后缀（即在若干个后缀状态中取最长的一个作为 fail 指针）。这里简单对比一下这里的 fail 指针与 KMP 中的 next 指针：
- 共同点：两者同样是在失配的时候用于跳转的指针。
- 不同点：next 指针求的是最长 Border（即最长的相同前后缀），而 fail 指针指向所有模式串的前缀中匹配当前状态的最长后缀。
因为 KMP 只对一个模式串做匹配，而 AC 自动机要对多个模式串做匹配。有可能 fail 指针指向的结点对应着另一个模式串，两者前缀不同。
没看懂上面的对比不要急，你只需要知道，AC 自动机的失配指针指向当前状态的最长后缀状态即可。
AC 自动机在做匹配时，同一位上可匹配多个模式串。
构建指针
下面介绍构建 fail 指针的 基础思想：（强调！基础思想！基础！）
构建 fail 指针，可以参考 KMP 中构造 Next 指针的思想。
考虑字典树中当前的结点 ， 的父结点是 ， 通过字符 c 的边指向 ，即 。假设深度小于 的所有结点的 fail 指针都已求得。
- 如果 存在：则让 u 的 fail 指针指向 。相当于在 和 后面加一个字符 c，分别对应 和 。
- 如果 不存在：那么我们继续找到 。重复 1 的判断过程，一直跳 fail 指针直到根结点。
- 如果真的没有，就让 fail 指针指向根结点。
如此即完成了 的构建。
例子
下面放一张 GIF 帮助大家理解。对字符串 i he his she hers 组成的字典树构建 fail 指针：
- 黄色结点：当前的结点 。
- 绿色结点：表示已经 BFS 遍历完毕的结点，
- 橙色的边：fail 指针。
- 红色的边：当前求出的 fail 指针。
- 例子
下面放一张 GIF 帮助大家理解。对字符串 i he his she hers 组成的字典树构建 fail 指针：
- 黄色结点：当前的结点 。
- 绿色结点：表示已经 BFS 遍历完毕的结点，
- 橙色的边：fail 指针。
- 红色的边：当前求出的 fail 指针。
- 我们重点分析结点 6 的 fail 指针构建：
找到 6 的父结点 5，。然而 10 结点没有字母 s 连出的边；继续跳到 10 的 fail 指针，。发现 0 结点有字母 s 连出的边，指向 7 结点；所以 。最后放一张建出来的图：
字典树与字典图
我们直接上代码吧。字典树插入的代码就不分析了（后面完整代码里有），先来看构建函数 build()，该函数的目标有两个，一个是构建 fail 指针，一个是构建自动机。参数如下：
- tr[u,c]：有两种理解方式。我们可以简单理解为字典树上的一条边，即 ；也可以理解为从状态（结点） 后加一个字符 c 到达的状态（结点），即一个状态转移函数 。下文中我们将用第二种理解方式继续讲解。
- 队列 q：用于 BFS 遍历字典树。
- fail[u]：结点 的 fail 指针。