简介

AC自动机即 Aho-Corasick automation，该算法在1975年产生于贝尔实验室。自动机是用来处理多串匹配问题的，即给你很多模式串，再给你一段MSG，让你在文章中找这些模式串是否出现过，在哪出现。AC自动机思想简单来讲就是在Trie上进行KMP匹配，所以先要知道Trie数据结构和KMP算法。

构造trie树

Trie是一颗字典树，由所有模式串的所有字元(字元可以是一个完整的字或者符号——多字节，也可以是一个字节)按线索构建成一颗多叉树。比如有模式串：

图1 模式串

可构建成如下的字典树：

图2 字典树

图2 中：0节点为树根节点；红色节点为模式终止节点，表示该节点可匹配到模式，但只是表示某个模式的结束，并不意味着匹配过程终止。

假设我们现在要对串“yshersayd”进行匹配，找出该串的所有模式串。一般的做法就是从一个指针i指向串的开始匹配位置。

首先i = 0：这时用串 [i, len(s)] 即“yshersayd”进行匹配，没有匹配；i++：这时用串[1,len(s)]即“shersayd”在单词树中匹配，得到得到匹配“she”；再i++：这时用串 [2,len(s)]即 'hersayd' 在单词树中匹配，得到匹配 'he' 和 'her'再 i++：依次进行。

易知算法最坏复杂度为O(nm)，n为主串的长度，m为模式串平均长度。这种做法每次都要从MSG的下一个字符开始检测余下的串(需每次回退MSG的指针)。

熟悉KMP算法的人都知道KMP算法中有一个失效函数，即某次模式匹配失败后不需要回退MSG指针，只要根据失效函数回退模式指针即可。AC算法也是如此，不过AC算法中直接称为失效指针。下面的一系列图将演示如何建立图5中的trie树的每个节点的失效指针，也就是建立有限自动机DFA的过程。

建立有限自动机DFA(失效指针)

说明:

1、失效指针是指：MSG匹配到trie的某个节点失败(该节点已经是叶子节点)后，接下来的匹配从trie的哪个节点继续进行。

2、下面的系列图中：紫色有向线表示失效指针的指向，每个节点都有失效指针，未标识出来的失效指针表示直接指向0节点。

3、必然的，0节点的每个子节点的失效指针都指向0节点。

4、每个节点有一个子节点表，指向256个子节点，对应一个字节的256个状态。

4、采用BFS(Breadth First Search)的搜索方式为每个节点建立失效指针。队列方式，Q(B、...、A)，A表示队头，B表示队尾

5、核心思想：从节点递级往父节点搜索。接下来的过程将慢慢深化这个思想。

6、为简化起见，下文只以纯英文举例。

7、每一个模式的每一个字符都表示一个节点。

8、AC_FAIL_STATE表示-1

先构建trie树。

上述例子中加上0节点，一共有13个节点。

第一步：所有节点的的子节点表元素NextState[i] i∈[0,255] 都置AC_FAIL_STATE，表示子节点不存在

第二步：用所有模式串初始化每个节点的状态表：

对于第一个模式SHE，S、H、E分别占用第1、2、3节点，则0节点的0.NextState[S] = 1，S.NextState[H] = 2, H.NextState[E] = 3.

对于第二个模式HE，H、E分别占用第3、4节点，则0节点的0.NextState[H] = 3, H.NextState[E] = 4.

对于第三个模式SAY, S已经出现在0的子节点，则A、Y占用5、6节点，S.NextState[A] = 5, A.NextState[Y] = 6.

依次类推，当处理完所有的模式后，就建立了如图3所示的trie树。且每个节点子状态表的都建立完毕：如0节点的有效子节点为S H A，其他子节点都为AC_FAIL_STATE

第三步：将0节点的所有无效子节点都置0，以便构造失效指针(终止向上搜索)。

再构造失效指针。

1、0节点的所有子节点的失效指针都指向0节点，并将子节点表中的有效子节点(A H S)入队列(按字节码顺序)，得到Q(S、H、A)。

图 3 前缀树

2、A出队，并将A的有效子节点Y入队，得到Q(Y、S、H)，并需建立A的有效子节点(仅为Y)的失效指针(此时为-1)

向上搜索Y节点的父节点A的失效指针的NextState[Y]，也即0的NextState[Y].发现为0(构造trie树的第三步目的)，退出搜索。

Y的失效指针指向0.

此刻 A的子节点表有256个元素，除Y了其他元素目前指向AC_FAIL_STATE。

思考一个问题，假如匹配的时候，现在处于A节点，MSG的下一个字符是S，为A的无效节点，此时，匹配失败，应该回退到哪里呢？

答案是回退到A的失效节点0对应的S节点。故A的无效子节点指向A的失效指针的对应节点。

3、H出队，并将H的有效子节点E入队，得到Q(E、Y、S)，并需要建立H的有效子节点(仅为E)的失效指针(此时为-1)

向上搜索E节点的父节点H的失效指针的NextState[E]，也即0的NextState[E].发现为0(构造trie树的第三步目的)，退出搜索。

H的失效指针指向0.

4、S出队，并将S的有效子节点A、H入队，得到Q(H、A、E、Y)，并须建立S的有效子节点(A、H)的失效指针(此时都为-1)

向上搜索A节点的父节点S的失效指针的NextState[A]，也即0的NextState[A].发现为X(构造trie树的第二步中模式处理模式AYD时给A分配的编号)，退出搜索。

A的失效指针指向0的子节点A.如图4所示。

类似，H的失效指针指向0的子节点H，如图5所示。

图 4

图 5

5、Y出队，D入队，类似，D的失效指针指向0

6、E出队，R入队，类似，R的失效指针指向0

7、A出队，Y入队，类似，Y的失效指针指向如图 6 所示。

图 6

8、H出队，E、R入队，类似，E的失效指针指向如图7所示.

图 7

依次类推,直到队列为空。至此，AC状态机就已经建立好了。

现在我们以图7所示的trie树来重新匹配MSG “yshersayd”。

1、MSG指针 y; trie指针为0，0.NextState[y] = 0;

2、MSG指针 s; trie指针为0, 0.NextState[s] 存在。

3、MSG指针 h; trie指针为S，S.NextState[h] 存在。

4、MSG指针 e; trie指针为H，H.NextState[e] 存在，并且是终止节点 匹配到SHE

5、MSG指针 r; trie指针为E，E.NextState[r] = E.AC_FAIL_STATE.NextStae[r](失效指针的作用。构造失效指针第2步蓝色加粗部分所述)存在，并且是终止节点，匹配到ER

6、MSG指针 s; trie指针为R，R.NextState[s] = R.AC_FAIL_STATE.NextState[s], R的失效指针是0,0.NextState[s]存在。

7、MSG指针 a; trie指针为S……

依次类推即可。

基于AC算法的扩展用途(脏词替换)

从上述匹配过程可以看出，对于输入串sher来说，只能匹配到两个模式：she和er。但实际上，sher串中还存在一个模式he。但是对于脏词检测来讲，只要能匹配到脏词即可，无须担心其他的操作。如果想要把一个字串的所有模式都找出来，而且做最长串替换的话，需要对在上述构造DFA的过程中增加一些操作。

当定位到一个节点的失效指针的时候，如果失效指针是终止节点，则将失效指针的匹配列表复制到该节点的匹配列表即可。如图7所示，假如“A”也是一个模式，则0节点的A子节点是一个终止节点，0节点的孙子节点A不是一个终止节点，但是该节点拥有匹配列表，表明此处也可匹配到模式。