前置知识
引入
往简单了说，AC自动机其实就是在字典树上搞KMP思想。它能够快速实现在一个文本串中匹配多个模式串。
思路
我们都知道，KMP算法中有一个 nxt 数组，用来处理匹配失败后状态的转移。AC自动机同样有一个这东西，叫做“失配指针”。
但是由于AC自动机匹配多个串，它跳转的不是前缀函数，最长的相同前后缀云云，而是所有状态中和当前状态的后缀相同的最长后缀，这就是说，它可能跳到一个不同的模式串上，只要这个模式串能匹配更多的后缀。
求失配指针
其实它的过程和KMP十分类似：
- 如果新出现的字符在这里能够继续匹配，或者不能继续匹配但是回到了状态
0，那么这里就是它失配指针对应的位置。 - 否则当前状态同样没能匹配，沿着当前状态的失配指针继续向前寻找。
以 i，he，his，she 和 hers 生成的字典树为例：
<p id="info"></p>
<img id="img" src="/blog/images/ac-auto/1.png" style="" onclick="getNextImg()">
<input type="button" value="<" onclick="getProImg()"/>
<input type="button" value=">" onclick="getNextImg()"/>绿色的边是失配指针指向的状态；蓝色的边是当前的失配指针；红色的边是求失配指针的过程。
字典图
但是我们可以对上面的思路加以改进。
仔细想一想，对于多个模式串的情况，其实不需要拘泥于仅仅一种失配的情况，而是对于这个节点接下来所遇到的所有可能字符，包括能匹配的和不能匹配的，进行预处理。
这样，我们就能够构造出一个字典图。字典图不仅包含了原来字典树的边，还增加了不同匹配情况所要跳转的位置，所以每个状态都能连出26（对于只有小写字母）条边。
<p id="info2"></p>
<img id="img2" src="/blog/images/ac-auto/1.png" style="" onclick="getNextImg2()">
<input type="button" value="<" onclick="getProImg2()"/>
<input type="button" value=">" onclick="getNextImg2()"/>（这里将每个点连出的边分开展示，方便观察。* 符号指所有未指定连边的字符。）