1.应用场景
假设您有一个文本（nwords）和大量关键字（mkeywords），您如何快速找到所有关键字？
简单实现，可以将每个关键字与文本进行比较，伪代码如上图，这样时间复杂度为O(n*m)，是非常缓慢的，有没有更高效的算法实现呢？
2.原理介绍
年，贝尔实验室的AlfredAho和MargaretCorasick发现了一种只扫描一遍文本就能完成这项任务的算法，该算法依据他们的名字命名为Aho-Corasick匹配算法，简称AC算法。该算法通过有限自动机巧妙地将字符比较转化为状态转移，此算法的时间复杂度与关键字的数目无关，只跟文本长度有关，其时间复杂度为O(n)，优于O(n*m)，匹配效率提升m倍。
AC算法实现分为两步：
第一步，我们将多个关键字构造成一个有限状态模式匹配机。第二步，我们将文本字符串作为输入送入模式匹配机进行匹配。
2.1.构建模式匹配机
在构建模式匹配机阶段，AC算法需要建立三个核心函数，分别为转向函数goto，失效函数failure和输出函数output。下面通过多关键字{he,she,his,hers}来介绍匹配机构建过程。
转向函数(g)
指的是一种状态之间的转向关系。g(pre,x)=next，状态pre在输入一个字符x后转换为状态next，如g(1,e)=2。如果在模式串中不存在这个的转换，如g(5,r)，怎么办呢？这个需要由失效函数来处理。
失效函数(f)
失效函数为AC算法的核心，指的是在失效情况下状态之间的转向关系，即当出现失效时，根据模式含有其他模式的前缀自动切换到某个状态。如上图模式串1含有模式串2的前缀，当匹配到a位置时，模式串1匹配失效，则跳转到模式串2进行匹配，而不用回到初始状态（0号状态）重新开始匹配。比如she模式是含有hers模式的前缀he，当在状态5匹配失效时跳转到状态2继续匹配。
失效跳转状态可通过递归推导获得：
f(与状态0直连状态)=0//f(1)=f(3)=0f(current)=g(f(pre),x)//f(4)=g(f(3),h)=g(0,h)=1
举例说明：
比如g(5,r)=fail，g(5,r)=g(f(5),r)，f(5)=g(f(4),e)=g(g(f(3),h),e)
状态3对应字符s，没有其他模式的前缀，切换到状态0，即f(3)=0
f(5)=g(f(4),e)=g(g(f(3),h),e)=g(g(0,h),e)=g(1,e)=2，
g(5,r)=g(f(5),r)=g(2,r)=8
最终结果：
输出函数(output)
指的是状态和模式串之间的一种关系。output(i)={P}，表示当状态机达到状态i时，模式串P中的所有模式串已经完成匹配。比如达到状态5，则模式串she和he匹配成功。
完整模式匹配机如下图。
2.2.进行匹配
假设待匹配文本为hisshers，那么状态转移为：0-1-6-7-3-0-3-4-5-2-8-9，文本仅扫描了一遍，依次输出结果his、she、he、he、hers。
3.代码实现
3.1.Python版本
核心数据
核心流程
3.2.C/C++版本
snort2（C）/snort3（C++）有ac算法实现，可通过snort