月更博主又来送温暖啦QwQ
今天我们学习的算法是AC自动机。AC自动机是解决字符串多模匹配问题的利器，而且代码也十分好打=w=
在这一篇博客里，我将讲解AC自动机是什么，以及怎么构建一个最朴素的AC自动机。（不知道为什么我写出来的AC自动机常数就是大得要命=。=）
前置知识首先你一定要对Trie树以及KMP了如指掌，尤其是要明白KMP中失配数组(next或fail数组)的本质:利用已经匹配过的部分，跳过重复的匹配，达到快速匹配的目的。
AC自动机是什么大家都知道KMP可以用于在一个大字符串（文本串）中寻找另一个小的字符串（模式串），那么如果有n个模式串，要你把它们全部在文本串中找出来呢？当然，我们可以做n次KMP（别小瞧30分哦），但是其效率并不能差强人意。这个时候，我们可以尝试把模式串做成Trie树，似乎可以提高效率。
比如说，我们有5个模式串：she,shr,say,he,her,那么它们所建出来的Trie树应该是长成这样的：（红色节点表示单词的结尾）
那么，怎么用它来匹配呢？如果我们把文本串的每一个点都作为起点放到Tire树上匹配，它的复杂度将会是...我要你Tire树有何用(╯‵□′)╯︵┻━┻
既然这样，那么如果只把文本串的第一个字符为起点，会发生什么呢？
你以为会是这样的：
完美！
然而实际上却是这样的：
问题很明显，当我们匹配完she时，he其实也被匹配到了。所以我们希望这棵Trie树上能够加点东西，让它可以达到下面的效果：
上图中，红色的箭头就是失配指针——fail指针。它表示文本串在当前节点失配后，我们应该到哪个节点去继续匹配。很显然，对于每个节点，我们要找到这个节点-代表的字符串-在树上所有的节点-表示的字符串中-能找到的最长的后缀，意思就是“我当前匹配到了这个点，我也相当于匹配到了的节点（中的深度最大的节点）。”比如说，在我举的例子中，当我们匹配到了she时，我们在树上走的路径也包含了he，he是she的一个后缀。我们在she上失配，至少说明我们已经匹配到了he，于是就可以跳到代表he的节点上继续匹配。
到这里，你是不是发现fail指针和KMP中的next指针简直一毛一样？它们都被称为“失配指针”。将Trie树上的每一个点都加上fail指针，它就变成了AC自动机。AC自动机其实就是Trie+KMP，它可以用来解决在文本串中寻找很多模式串，即多模匹配问题。
对于一开始的5个单词，它们所构建出的AC自动机就长这样（没有画出红色箭头的点，其fail指针都指向根节点）：
显然，我们要做的就是快速地求出所有点的fail指针。我们以bfs的顺序依次求出每个节点的fail，这样，当我们要求一个节点的fail时，它的父亲的fail肯定已经求出来了。若当前节点为A，其父节点为B，B的fail为C，那么C所代表的字符串一定是B的最长的后缀。如果C有一个儿子D的字符与A的字符等同，那么显然D所代表的串（C加一个字符）就是A所代表的串（B加一个字符）的最长后缀。如果C没有一个儿子，使其字符与A的字符等同呢？很简单，只需要再访问C的fail就行了。如此反复，直到A的最长后缀找到，或者A的fail指向根节点为止。（A在Trie树中没有后缀，乖乖回到根重新匹配吧！）
为了解释得更清楚，我举一个例子。下面这幅图是我根据别的地方的图重新画的（n次转载？），出处我没找到_(:з」∠)_。节点是根据bfs序标号的。
步骤：
为了少一些特判，设置一个辅助根节点0号节点，0号节点的所有儿子都指向真正的根节点1号节点，然后将1号节点的fail指向0号节点。
找到2号节点的父亲节点的fail节点0号节点，看0号节点有没有为a的子节点。有，于是2号节点的fail指向1号节点。
找到3号节点的父亲节点的fail节点0号节点，看0号节点有没有为b的子节点。有，于是3号节点的fail指向1号节点。
找到4号节点的父亲节点的fail节点1号节点，看1号节点有没有为b的子节点。有，于是4号节点的fail指向3号节点。
同上。
同上。
同上。