13.ac自动机

AC自动机就是KMP算法拓展到多模式匹配之后的结果，是一棵带有“失配指针”的字典树。

AC自动机是一种典型的前缀搜索算法：

什么是有限自动机 (Deterministic Finite Automaton, DFA)呢？

**自动机(Automaton)**：就是一个代码块,只做一件事——接收输入值，和状态值，输出同为状态值的结果。

**有限(Finite)**：是指自动机接收、输入的状态种类是有限的。不然就是英菲尼迪了。

**确定(Deterministic )**：是指自动机的输出状态是单一的一个状态，不然就是NFA了。

                                                                 典型的DFA 

                                                                 典型的NFA 

AC自动机(Aho-Corasick automaton)算法于1975年产生于贝尔实验室，是一种用于解决多模式匹配问题的经典算法。常被用来做敏感词检测，后处理的替换模块也是基于此。

值得注意的是，AC自动机应当属于基于前缀搜索的非压缩字典树。

UNIX之中的grep就是用的这玩意实现的。

AC自动机的原理如下：

以模式串(替换列表)为his、hers、she为例，首先构建一个trie：

这时，我们就需要“失配指针”来帮忙了，为了节省匹配次数，不放弃已匹配过的部分，AC自动机之中加入了fail路径，又叫失配路径(指针)。失配指针能够在节点无法匹配下个字符的时候，转向其他节点。

那失配指针是如何构建的呢？

结果如下：

继续构建第二类：

继续构建第三

最终的结果如下：

那么构建完毕之后，如何搜索字符串呢？为了更好的说明匹配规则，我们往原来的trie之中多

插入一个”he”，则4号节点变为terminal。

当然了，实际上字符串匹配的传统算法还有很多：

能看到，该算法在搜索的时候，突出一个稳定，尤其是在于WM算法进行比较的时候，优势明显