多模式串匹配之AC自动机算法

1、算法）简介与c语言程序实现源码参考任侠 发布于 2011-03-2222:27:53一、概述AC自动机算法全称Aho-Corasick算法，是一种字符吊多模式匹配算法。该 算法在1975年产生于贝尔实验室，是著名的多模匹配算法之一。AC算法用于在一 段文本中查找多个模式字符串，即给你很多字符串，再给你一段文本，让你在文本 中找这些吊是否出现过，出现过多少次，分别在哪里出现。该算法应用有限自动机巧妙地将字符比较转化为了状态转移。此算法有两个 特点，一个是扫描文本时完全不需要回溯，另一个是时间复杂度为0（n）,时间复 杂度与关键字的数LI和长度无关，但所需时间和文本长度以及所有关键字的总长度 成正

2、比。AC算法有三个主要步骤，一个是字典树tire的构造，一个是搜索路径的确 定（即构造失败指针），还有就是模式匹配过程。学习AC自动机算法之前，最好先熟悉KMP算法，因为KMP算法与字典树 tire的构造很是类似。KMP算法是一种经典的单字符串匹配算法。二、AC算法思想AC算法思想：用多模式串建立一个确定性的树形有限状态机，以主串作为该 有限状态机的输入，使状态机进行状态的转换，当到达某些特定的状态时，说明发 生模式匹配。下图是多模式he/ she/ his /hers构成的一个确定性有限状态机，做儿点说 明：图2.11、该状态机优先按照实线标注的状态转换路径进行转换，当所有实线标注 的状态转

3、换路径条件不能满足时，按照虚线的状态转换路径进行状态转换。如：状 态0时，当输入h,则转换到状态1；输入s,则转换到状态3；否则转换到状态Oo2、匹配过程如下：从状态0开始进行状态转换，主串作为输入。如主串为：ushers,状态转换的过程是这样的:图2. 23、当状态转移到2, 5, 7, 9等红色状态点时，说明发生了模式匹配。如主串为：ushers,则在状态5、2、9等状态时发生模式匹配，匹配的模式 串有 she、he、herso定义：在预处理阶段，AC自动机算法建立了三个函数，转向函数goto,失效函数 failure和输出函数output,由此构造了一个树型有限自动机。转向函数，指的是一

4、种状态之间的转向关系。g(pre, x)二next：状态pre在 输入一个字符x后转换为状态next (上图中的实线部分)。如果在模式串中不存 在这样的转换，则next=failstateo失效函数，指的也是状态和状态之间一种转向关系。f(per)=next：是在比较 失配的情况下使用的转换关系。在构造转向函数时，把不存在的转换用failstate 表示，但是failstate不是一个具体的状态，状态机转换转换到failstate状态的 时候就不知道该往哪转了。所以就要在状态机中找到一个有意义的状态代替 failstate,当出现failstate状态时，自动切换到那个状态。这个状态节点应该具

5、有这样的特征：从这个状态节点向上直到树根节点(状 态0)所经历的输入字符，和从产生failstate状态的那个状态节点向上所经历的 输入字符串完全相同。而且这个状态节点，是所有具备这些条件的节点中深度最大 的那个节点。如果不存在满足条件的状态节点，则失效函数为0。累死了。举例子说吧，对状态9输入任何一个字符都会产生failstate状 态，需要失效函数。状态3向上到状态0经过的输入字符串为s；而山状态9向上 的输入字符串为sreho字符串s相同，并且状态3是满足此条件的唯一节点，则f(9)=3o说来说去，失效函数就是要干这么件事儿：图2. 3意思就是说，在比较模式串1发生失配时，找一个模式串2

6、,使得P20.j-1 = Pli-j+l.io然后继续比较模式串2。看上面那个图，想起点儿什么东西 没有？对了，是KMP算法。有人说AC算法就是KMP算法在多模式匹配情况下的扩 展。输出函数，指的是状态和模式串之间的一种关系。output(i)二P,表示当状 态机到达状态i时，模式串集合P中的所有模式串可能已经完成匹配。例:模式串为:he/ she/ hers/ his时，如图2. 4所示。转向函数:LEJ图2.4失效函数:图2. 5输出函数:图2.6这个比较好理解，就是把要匹配的一些字符串添加到树结构中去。树边就是 单词中的字符，单词中最后一个字符的连接节点添加标志，以表示改节点路径包含 1

7、个字典中的字符串，搜索到此节点就表示找到了字典中的某个单词，可以直接输 出。Trie是一个树形结构的状态装换图，从一个结点到它的各个子结点的边上有 不同的标号。Trie的叶子结点表示识别到的关键字。当我们的模式串在Tire上进行匹配时，如果与当前节点的关键字不能继续匹 配的时候，就应该去当前节点的失败指针所指向的节点继续进行匹配。例子：某字典P二he, she, his, hers对应的字典树如下图：图3. 1图中有数字的节点到根节点的路劲正好对应字典中的字符串，数字表述单词在字典中的顺序，也可以是其他标志。四、搜索路径的确定我的理解是：利用后缀字符串来确定。后缀字符串就是某个字符串的后面的

8、部分。比如abcde的后缀字符串有bcde, cde, de和e。假定目标字符串为ushers,字典为上图（图1）所示。搜索过程U标字符串指针指向的字符和字典中的字符会有以下儿种惜况：a. 当前字符匹配。表示从当前节点沿着树边有一条路径可以到达LI标字符， 此时只需沿该路径走向下一个节点继续匹配即可，LI标字符串指针移向下个字符继 续匹配；如：当指针指到S处，此时字典树指针处于根，要从根到s处，可以看到图 中有一条从根经s连接到的节点，因此字典树节点指针指向此节点，H标字符串指 针移动到下一字符h继续匹配：显然当前节点有一条经h连接到的节点，于是重复 操作到有数字标志的节点2处，表示已找到，该

9、匹配字符串就是"she",输出该字 符串的位置后，U标字符串指针增1指向字典指针指向数字2节点，进行下 次匹配。b. 当前字符无匹配。表示当前节点的任何一条边都无法达到要匹配的字符， 此时不能沿现有路径前进，只能回溯，回溯到存在的最长的后缀字符串处，如果没 有任何后缀字符吊匹配则回溯到树根处。然后从当前回溯节点判断是否可以到达LI 标字符串字符。如：接上，由于数字2节点无经"r"的连接，因此回溯，she的后缀字符串he 在字典树中，因此字典树指针指向带有数字1的标志节点，由于带有标志，直接输 出该节点HE"（存疑，很多文章没有提到此处需要输出，

10、正常路径移动的字典指针 节点要判断是否可以输出，那么山回溯路径改变的字典指针指向的节点要不要判断 是否输出？），然后从数字1节点判断是否有经"r"到下一节点的路径，显然图中 有。因此字典树节点指向下一节点，重复以上操作，最后找到hers，此时匹配搜 索也结束了。以上两种惜况直到LI标字符串指针直到末尾结束匹配。在匹配过程中遇到有 标志的节点说明找到了字典中的某个词，可以直接输出。输出说明：每次H标串指针移动前都需要判断当前节点是否可以输出，并递归的判断当 询节点回溯路径上的节点是否可以输出（其实就是判断所有后缀字符串，she匹配 时，其后缀he也会匹配，即使she不匹配，其

11、后缀he也可能匹配，因此需递归判 断后缀字符串），直到树根结束递归。山于固定字典的字符串的后缀字符串都是已知的，因此可以在字典树结构中 存储匹配失败的路径方向，因此只要字典树构造完毕，就可以根据字典树的路径进 行匹配了，效率非常快。以上就是我对该算法的全部过程的理解，疏漏之处在所难 免。附录：附1：含匹配失败的悄况的路径选择的字典树，实线表示匹配成功的正常路径，虚 线表示失败的回溯路径图附11附2： AC算法的伪代码实现描述T为目标字符串，长度为m, q为字典树的节点指针，g函数返回从节点q经 过路径Ti到达的下一节点指针，f函数返回节点q的回溯节点指针。flag判断 节点是否为标志节点q :

12、二 0; / initial state (root)for i ：= 1 to m dowhile g(q,Ti) = NULL doQ ：= f(Q)； / 回溯Q ：= g(Q, Ti); 前进node:=q;while(node!=root) if flag (node) exist ; then print i, out (node):node = f (node) ;/查找回溯节点end for;附3：一个简单的AC算法实现源码示例参考:/*程序说明：多模式串匹配的AC自动机算法自动机算法可以参考柔性字符串匹配里的相应章节，讲的很清楚*/ncludestdio. h>#inc

13、lude <string h>const int MAXQ = 500000+10;const int MAXN = 1000000+10;const int MAXK二26;/自动机里字符集的大小struct TrieNodeTrieNode* fail;bool danger;/该节点是否为某模式串的终结点int ent;以该节点为终结点的模式串个数TrieNode ()fail 二 NULL;memset(next, NULL, sizeof(next);danger = false;ent = 0;*queMAXQ, *root;/文本字符串char msgMAXN;int

14、 X;void Trielnsert(char *s)int i 二 0;while(si) int idx = s ia ;辻(ptr-nextidx二二 NULL)ptr->next idx = new TrieNodeO ; ptr = ptr->nextidx;i+；ptr-danger = true;ptr->cnt+;void Init()int i;char s 100;for(i = 0; i < X; i+) scanf (“s", s);Trielnsert (s); void Build_AC_Automation()int rear =

15、 1, front = 0, i;que0 = root;root->fail 二 NULL;while(rear != front)TrieNode 水cur = quefront+;for(i 二 0; i < 26; i+)辻(cur->nexti != NULL)if(cur = root) cur->nexti-fail = root;elseTrieNode *ptr = cur->fail;while(ptr != NULL)辻(ptr->nexti != NULL)cur->nexti->fail = ptr->nexti;

16、 if(ptr->nexti->danger = true) cur->nexti->danger = true;break;ptr = ptr->fail;if(ptr = NULL) cur->nexti->fail = root;querear+ = cur>nexti;int AC_Sedrch()int i = 0, ans = 0;TrieNode *ptr = root;while(msgi)int idx 二 msgia ;while(ptr->nextidx = NULL && ptr != root) ptr = ptr->fail;ptr = ptr->nextidx;if(ptr = NULL) ptr = root;TrieNode *tmp =