经典中英文模式匹配算法比较.doc

经典中英文模式匹配算法比较 本科生毕业论文题目名称 经典中英文 模式匹配算法比较 学生姓名 张 宏 学号 20114042034 学 院 信息科学与工程学院 专业年级 2011计科1 指导教师 莫礼平 职称 高级实验师 填写时间 2014年9月28日 吉首大学教务处制经典中英文模式匹配算法比较目录摘要1Abstract1第一章 绪论21.1概述21.2本文的研究内容及论文组织结构3第二章 模式匹配算法32.1模式匹配的定义32.2经典模式匹配算法KMP算法4第三章 常用的单模式匹配算法53.1 一种改进的KMP算法53.2 BM算法6第四章 常用的多模式匹配算法124.1 AC算法124.2 WM算法19第五章 大规模图数据库上的模式匹配算法225.1数据存储的方式及图的访问接口225.2模式匹配算法的实现23第六章 一种适合中文的模式匹配算法246.1 完全哈希表和状态矩阵存储方式的不足246.2 一种带跳转距离的邻接链表存储方式256.3 AC_SC算法描述27第七章 实验测试及结果分析307.1 实验环境307.2 实验方案307.3 实验结果与分析31结语32参考文献3434摘要模式匹配作为网络信息安全的核心技术之一，其效率直接影响整个系统的性能，一直也是学术界和工业界关注和讨论的热题。在当下，随着互联网的普及，网名数量呈几何增长，大规模数据甚至海量信息给网络信息安全带来了新的挑战，所以研究模式匹配算法具有重要的学术意义以及广阔的应用前景。本文分析了KMP、BM、AC和WM四种经典模式匹配算法，并提出了KMP算法的一种改进策略。在面临复杂数据难以管理新形势下，本文还介绍了一种大规模图数据库上的模式匹配算法。由于对中文模式匹配的需求日益增加，本文也介绍了一种适合中文环境的模式匹配。最后，以codeblocks编译器为工具，分析比较了四种经典模式匹配算法的性能。关键字：模式匹配；单模式匹配；多模式匹配；大规模；中文环境。AbstractPattern matching，as one of the core technologies of network information security, has been affecting the performance of the whole system, and has been being the hot topics that the academia and industry pay attention to and discuss. At present, with the popularization of Internet, net population showed a geometric growth, large-scale data and even mass data of network have brought new challenges to information security. As a result, the research of pattern matching algorithm has important academic significance and broad application prospects.In this paper, four classical pattern matching algorithms for KMP, BM, AC and WM are analyzed, and an improved KMP algorithm is come up. And under the new situation of the complex data been difficult to manage, this paper also describes a large-scale pattern matching algorithm based on the map database. With the increasing demand for Chinese environment pattern matching, this paper actually introduces a pattern matching for this condition.At last, the performance of four classical pattern matching algorithms is analyzed under the CodeBlocks compiler.Key words：pattern matching; simple pattern matching; multiple pattern; large scale; Chinese environment. 第一章 绪论1.1概述1.1.1研究背景与意义随着Internet技术的广泛应用和深入研究，特别是互联网的普及，国民经济信息进程的推荐、网络应用的发展和普及，各行各业对计算机网络的依赖程度越来越高。搜索问题是计算机科学中最基本问题，串匹配问题就是在一个符号序列中查找另一个或者一些符号序列的搜索问题。在我们使用计算机的过程中，使用模式串匹配技术的例子随处可见，例如任何文本编辑、处理应用程序都包括了模式串搜索。模式串匹配技术的发展是与其应用密切相关的。模式串匹配技术最直接的应用时构建数据的全文检索系统，以及图书文献目录的查询系统；随着网络技术和生物技术的不断发展，特别是在信息安全和生物信息学领域上，人们对模式匹配技术的要求不断提高。1.1.2模式匹配技术产生、发展与研究现状最早的模式匹配算法是经典的单模式匹配算法是由Knuth、Morris和Pratt于1977年提出的KMP算法1该算法对文本串从左到右匹配，一旦失配，就利用“部分匹配”将模式串向右“滑动”若干个字符后继续与文本串的当前字符进行匹配，直至匹配（不）成功。同一年，Boyer和Moore提出了BM算法2该算法利用坏字符移动规则和好后缀移动规则计算模式串的左移的距离，与KMP算法的最大的不同之处在于，当文本串与模式串在某个位置对齐之后，KMP算法是从对齐位置向后依次执行匹配（不一定是模式串的第一个元素）。而BM算法是从模式串的末尾位置（一定是模式串的最后一个元素）向前与文本串依次执行匹配。最早的多模式匹配算法是由A.V.Aho和M.J.Corasicky于1975年提出的AC算法3 该算法结合了KMP算法的思想和有限状态自动机理论，匹配之前先对模式串集合构造有限状态自动机，匹配过程中通过状态转移表扫面一边文本串，就可识别出所有模式串。1994年Wu Sun和Manber提出了另一种多模式匹配算法WM算法4 该算法融合了BM算法坏字符规则和完全Hash散列的思想，利用前缀表和哈希散列表，对所有的模式串进行处理，只扫描一遍文本即可识别多个模式串。近年来由于互联网的普及，大数据的大量深入研究，对模式匹配算法提出了更高的要求，文献5提出了一种应对大规模数据的模式匹配算法。对于复杂数据的模式匹配，文献6提出了一种大规模图数据库上的模式匹配。随着中文模式串匹配需求的增加，适合中英文环境的模式匹配成了研究热题，文献7中提出了一种基于有限状态自动机的中文多模式匹配算法，该算法在保证合理的内存空间占用下，大幅提升了算法的匹配性能。1.2本文的研究内容及论文组织结构本文旨在比较KMP、BM、AC及WM四种经典的模式匹配算法，并作相应的性能分析，以达到了解不同需求环境下对算法的选择问题。在本文的前四章中将详述以上四种算法，并对四种算法进行编码实现。在本文的第五章将介绍文献6中提到的“大规模图数据库上的模式匹配”，在本文的第六章将介绍文献7中提到的“基于有限状态自动机的中文多模式匹配算法”。在本文的第七章，将对四种经典的模式匹配算法进行实验测试和结果分析。第二章 模式匹配算法2.1模式匹配的定义模式匹配（Pattern Matching）指“模式串”（Pattern）在“文本串”（Text）中的一个或全部出现位置的操作。通常根据算法同时所匹配模式串的数量，把模式匹配算法分为“单模式匹配算法”和“多模式匹配算法”两类，以下是它们的数学描述：单模式匹配算法已知：有限字符集合，模式化串P=p1p2pm (pr,1rm)，文本串T=t1t2tn（t,1sn），其中n m.求解：T中是否存在位置i，使得ti+k = pk（1km）.多模式匹配算法已知：有限符号集，模式串集合P=p1,p2pL，模式串集中模式个数为L。其中pj=pj 1pj2 pjmj，1jL，长度为mj；文本串T=t1t2。tn，长度为n，n mj。所有字符均取自集合。求解：通过对模式串集合P的预处理，将T同时与P中全部模式串相匹配，查找P中所有模式串在T中所出现的位置，即查找T中位置i，使得ti+k = pjk（1kmj）。下表是本文中用到的主要参数意义：表2.1 本文用到的主要参数意义说明符号意义及说明n文本串的长度，时间复杂度分析时表示问题规模 m模式串的长度i文本串的当前位置j模式串的当前位置 k子串（前缀/后缀）的长度 T文本串中的某个字符p模式串中的某个字符2.2经典模式匹配算法KMP算法2.2.1 算法的基本思想KMP算法可以在O(n+m)的时间数量级上完成串的模式匹配操作，当文本串中的第i个字符与模式串中的第j个字符“失配”时，文本串种的第i个字符应与模式串中的第nextj个字符比较，而不需要回溯。其中next函数的定义为：1) 当j=1时：nextj = 0;2) 当p1k-1=pj-k+1j-1集合不空时：nextj = MAXk|1kj 且 p1k-1=pj-k+1j-1. 3) 其他情况：nextj = 1.根据上述思想，写成函数代码为：代码2.1 构建nextint make_next(char *p, int *next, int m) int i = 0; int j = 1; *next = 0; while(i n,n0(m为文本串的长度,n为模式串的长度)的情况下，如果模式串没有在文本串中出现，那么改进后的算法可以比较剩下的字符数来判断是否匹配成功，因为如果剩下的字符数目不够（比模式串要短）的话，那么匹配一定是失败的。根据上面的经验很容易能够提出两种解决方案：方案一把模式串逆转，再根据原来next函数求出跳转表来进行匹配。方案二更具原有的next函数重新写一个next_new函数，再求出相应的跳转表来进行匹配。当n0的时，将模式串逆转需要多消耗一个字符串来存储逆转后的模式串，那么在每次调用此算法时都需要多消耗跟模式串一样的存储空间，这样就浪费了很多空间，还能想到除此之外，方案一每次都要至少遍历模式串两次，而方案二只需遍历一次就够了。所以不采用方案一，而采用方案二。下面给出方案二的next_new函数的求法：将模式串的末字符看成首字符仿照next函数实现next_new函数。代码3.1 构建next_newvoid make_next_new(char *p, int *new_next, int n) int i = n-1; int j = -1; int k = n; *new_next = -1; while(i 0) if(j = -1 | *(p+i)= *(p+k-j-1) ) i-;j+; if( *(p+i) != *(p+k-j-1) *(new_next +n-i-1) = j; else *(new_next+n-i-1) = *(new_next+j); else j = *(new_next +j); 3.1.2 算法的时间复杂度分析因为next_new函数仿照的是next函数写成，所以时间复杂度与next函数一样都是O(n)，并且在某种程度上能够提高模式匹配的效率，另外，还能提早结束不必要的匹配。3.2 BM算法 1997年,Robert S.Boyer 和Strother Moore提出了另一种时间复杂度为O（n）的算法2，在某种场合下，其性能比KMP还要出色。3.1.1 算法的基本思想BM算法使用了两张表一张坏字符表（delta1）和一张好后缀表（delta2），下面给出BM算法的一次匹配过程：假设：T=” WHICH-FINALLY-HALTS.-AT-THAT-POINT”，P=“AT-THAT”则：BM算法的一次匹配过程如下表3.1 BM算法的一次匹配过程1234567891011121314151617181920212223242526272829303132333435WHICH-FINALLY-HALTS.-AT-THAT-POINT1AT-THAT2AT-THAT3AT-THAT4AT-THAT5AT-THATBM算法与KMP最大的区别在于，当模式串与文本串在某个位置对齐后，KMP算法对齐位置向后一次执行匹配（不一定是模式串的第一个元素）。而BM算法是从模式串的末尾位置（一定是模式串的最后一个元素）向前与文本串依次执行匹配，上述的示例中，在第4次模式串移动之后就发现了匹配的模式串。第一次， P1与T1对齐，从P7向前依次与T进行比较，但是第一次比较就发现T7=F，而F不是P中的字符，所以T中任何包含T7的子串都不可能与P匹配，所以这个时候可以直接把P滑动到T7之后，让P1与T8对齐，然后在有T14依次向前执行比较。第二次， T14=-，虽然-是模式串P中的字符，但是如果要T串中包含T14的字符串与P匹配，则至少要求T14与P中最后一个-对齐，而P串中只有一个-，所以将T14与P3对齐，然后再由T18向前依次比较。第三次， 虽然T18=P7=T，但是T17=L，L不是P串中的字符，所以直接将P1与T18对齐，再依次执行比较。第四次， T2324=P67，T22!=P5，且P67=P12，所以P12也是模式串的一个自包含后缀，所以将P1与T23对齐再向前执行匹配，此时，就发现了满足条件的匹配模式串T2329。上述示例使用到了BM算法中的所有跳转表，大幅加速了模式串向后滑动的过程，实现了模式的快速匹配。其中，第1，2，3次滑动使用的是坏字符移动规则，第4次使用的是好后缀移动规则。下面详述这两种规则：坏字符规则可以理解为一张这样的表，它以输入字符集的所有字符作为索引，每个输入字符c对应着一个值，表示如果文本串的当前位置字符c与模式串匹配失败，那么文本串当前位置可以向前滑动的步数为delta1c。这里可以与KMP算法next函数定义比较：nextj=k表示文本串（主串）的字符与模式串nextj处的字符继续比较。假设字符集合为” ABCDEFGHIJKLMNOPQRSTUVWXYZ-”，那么它对应的模式串P=” AT-THAT”的坏字符表为：表3.2 模式串P=” AT-THAT”对应的坏字符表ABCDEFGHIJKLMNOPQRSTUVWXYZ-delta1177777727777777777707777774坏字符表的定义为，对于输入的字符集合中的字符c，如果c不在模式串中，则delta1c=patlen（模式串的长度），如果c在模式串中，则delta1c=j-i，其中，j是模式串最末元素的索引值，i是字符c在模式串中最右出现的位置。下面给出坏字符表delta1构建的代码：代码3.2 构建delta1void make_delta1(int *delta1, const char *pat, int patlen) int i; for (i=0; i ALPHABET_LEN; i+) / #define ALPHABET_LEN 256 delta1i = patlen; for (i=0; i patlen-1; i+) delta1pati-A = patlen-1 - i; 所谓好后缀移动规则，就是对于P1.j，存在长度为k的子串，满足Pm+1.m+k=Pj-k+1.j，其中kj，0mj-k。以字符串BCDBCDABCDABCD为例，P7.10就是一个包含后缀，因为P7.10=P11.14。定义数组pre，与P中的元素一一对应，对于P中的元素Pi，prei是使得Pk+1j-1=Pi+1j，且Pk!=pi的k的最大值，如果不存在这样的k，prei=patlen.P1214在模式串中的包含后缀P46，此时如果发现文本串Tn与模式串P11失配，就直接将P3与Tn对齐，然后再从Tn+11处向前依次与模式串进行匹配。文本串当前位置的跳转距离为delta2i=j-prei。在计算pre之前，先将prei初始化为patlen，对于Pi，如果不存在m使得Pm+1m+j-i=Pi+1j(m i)，且Pm!=Pi，则不修改prei的值，即还为prei=patlen；如果prei!=patlen，delta2i=j-prei；否则，对于Pi(j-ic)的情况，delta2i=patlen+j-i-c,其中c是满足P1c=Pj-c+1j（c0）的最大值，如果不存在这样的c，c=0。模式串种最末元素的delta2值固定为1。下表为”BCDBCDABCDABCD”对应的pre值和delta2值：表3.3 ”BCDBCDABCDABCD”对应的pre值和delta2值1234567891011121314BCDBCDABCDABCDprei1414141414141414141431414delta2i242322212019181716151113121下面给出通过pre构建delta2代码：代码3.3 构建delta2void make_delta2(int* delta2,const char* pattern, int pattern_length)unsigned int i, j, c;for(i = 0; i pattern_length - 1; +i)delta2i = pattern_length;/初始化pattern最末元素的好后缀值delta2pattern_length - 1 = 1;/*此循环找出pattern中各元素的pre值，这里delta2数组先当作pre数组使用*/for(i = pattern_length -1, c = 0; i != 0; -i)for(j = 0; j i; +j)if(memcmp(pattern + i, pattern + j, (pattern_length - i) * sizeof(char) = 0)if(j = 0)c = pattern_length - i;elseif(patterni - 1 != patternj - 1)delta2i - 1 = j - 1;/根据pattern中个元素的pre值，计算delta2值for(i = 0; i = c)delta2i -= c;现在可以根据delta1和delta2找出模式P1j：首先，将P1与T1对齐，然后Tj向前依次执行匹配。如果在Pi位置失配，则在好后缀表里用i查找滑动距离delta2i，在坏字符表中用Ti作索引，查找滑动距离delta1Ti，假设前者返回值为p,后者返回值为q，这时取其较大者MAX=pq?p:q，然后将Pj与Pi+MAX对齐，然后一次向前匹配，直到发现匹配，或者遍历整个文本串都没有发现模式串。下面给出BM算法实现代码：代码3.4 实现BMvoid BM (char *string, int stringlen, const char *pat, int patlen) int i; int delta1ALPHABET_LEN;/ #define ALPHABET_LEN 256 int *delta2 = (int *)malloc(patlen * sizeof(int); make_delta1(delta1, pat, patlen); make_delta2(delta2, pat, patlen); / The empty pattern must be considered specially if (patlen = 0) return string; i = patlen-1; while (i = 0 & (stringi = patj) -i; -j; if (j 0) free(delta2); return (string + i+1); i += max(delta1stringi-A, delta2j);/ #define max(a, b) (a b) ? b : a) free(delta2); return NULL;3.1.2 算法的时间复杂度分析BM算法中构建delta1的时间复杂度为O（n），构建delta2的时间复杂度为O（n2）。第四章 常用的多模式匹配算法4.1 AC算法1975年，A.V.Aho和M.J.Corasicky提出了AC算法3，可以保证对于给定长度为n的文本，和模式集合Pp1,p2pm，在O（n）的时间复杂度内找到所有的目标模式，而与模式集合的规模m无关。经典的AC算法由三张表构成goto表，fail表和output表。goto表是由集合模式P中的所有模式构成的状态转移自动机，对于集合Phe,she,his,hers，模式s(he)的非前缀子串he，实际上却是模式(he)，(he)rs的前缀。如果文本串Ti.i+2与模式she匹配，同时也意味着Ti+1.i+2与he，hers这两个模式的头两个字符匹配，所以此时对于Ti+3，我们不需要回溯文本串的当前位置，而直接将其与he，hers两个模式的第3个字符对齐，然后直接向后继续执行匹配操作。其对应的goto表为为：表4.1 Phe,she,his,hers对应的goto表对于给定的集合Pp1,p2,.pm，构建goto表的步骤是，对于P中的每一个模式pi1.j(1=im+1)，按照其包含的字母从前到后依次输入自动机，起始状态D0，如果自动机的当前状态Dp，对于pi中的当前字母pik(1=k=j)，没有可用的转移，则将状态机的总状态数smax+1，并将当前状态输入pik后的转移位置，置为Dppik = smax，如果存在可用的转移方案Dppik=q，则转移到状态Dq，同时取出模式串的下一个字母pik+1，继续进行上面的判断过程。这里我们所说的没有可用的转移方案，等同于转移到状态机D的初始状态D0，即对于自动机状态Dp，输入字符pik，有Dppik=0。理论介绍很繁琐，让我们以之前的模式集合Phe，she，his，hers说明一下goto表的构建过程。第一步，将模式he加入goto表：第二步，将模式she加入goto表：第三步，将模式his加入goto表：第四步，将模式hers加入goto表：对于第一和第二步而言，两个模式没有重叠的前缀部分，所以每输入一个字符，都对应一个新状态。第三步时，我们发现，D0p31=D0h=1，所以对于新模式p3的首字母h，我们不需要新增加一个状态，而只需将D的当前状态转移到D1即可。而对于模式p4其前两个字符he使状态机转移至状态D2，所以其第三字符对应的状态D8就紧跟在D2之后。下面给出构建goto表代码：代码4.1 构建goto表void BuildGoto(const vector& patterns)unsigned int used_states;unsigned int t;vector:const_iterator vit;string:const_iterator sit;for(vit = patterns.begin(), used_states = 0; vit != patterns.end(); +vit)for(sit = vit-begin(), t = 0; sit != vit-end(); +sit)if(_gotot(*sit)-a = 0)_gotot(*sit)-a = +used_states;t = used_states;elset = _gotot(*sit)-a;_outt.insert(*vit);接下来构建fail表，所谓fail表就是当我处在状态机的某个状态Dp时，此时的输入字符c使得Dpc=0，那么我们应该转移到状态机的哪个位置来继续进行。以输入文本shers为例，当输入到字母e时，我们会发现匹配模式(she)rs，对应与状态机的状态D5，然后输入字母r，此时我们发现D6r=0，对于字母r D6不存在有意义的跳转。此时我们不能跳转回状态D0，这样就会丢掉可能的匹配s(hers)。我们发现s(he)的后缀he是模式(he)rs的一个前缀，所以当匹配模式she时，实际也已经匹配了模式hers的前缀he，此时我们可以将状态D6转移到hers中的前缀he在goto表中的对应状态D2处，再向后执行跳转匹配。这一跳转，就是AC算法中的fail跳转，要实现正确的fail跳转，还需要满足一系列条件，下面会逐一说明。对于模式串she，其在字母e之后发生了匹配失败，此时其对应的模式串（回溯到状态D0）就是she。对于she来说，它有两个包含后缀（除字符串自身外的所有后缀），he和e，对于后缀he，将其输入自动机D，从状态D0可以转移到状态D2，对于后缀e，没有可行的状态转移方案。所以对于状态D5，如果对于新输入的字符c没有可行的转移方案，我们可以跳转到状态D2，考察D2c是否等于0。AC两人在论文中举出的例子，并不能涵盖在构建fail时遇到的所有情况，这里特别说明一下。前面我们说过，对于she的包含后缀e，没有可行的转移方案，此时如果模式串中还包含一个模式era，那么D5可不可以转移到状态D10去呢，实际上这是不行的，我们需要找到的是当前所有包含后缀中最长的满足条件者，如果D5对于失败的输入c优先转移到D10，那么对于文本串shers，很显然会漏掉可能匹配hers，那么什么时机才应该转移到D10呢，当我们处理模式串hers时，处理到D2时对于之前的输入he，其最长的包含后缀是e，将e输入自动机，可以转移到D10，所以在D2处发生匹配失败的时候才应该转移到D10。所以当我们在D5处匹配失败时，要先跳转到D2如果再没有可用的转移，再跳转到D10。这个例子同时说明，对于模式集合P的所有模式pi，我们需要处理的不仅是pi的所有包含后缀，而是pi的所有非前缀子串。以模式hers为例，其在2，8，9三个状态都可能发生匹配失败，所以我们要提取出hers的所有非前缀子串(e，er，r，ers，rs，s)，然后按照这些子串的末尾字符所对应的自动机状态分组（上例就可以分组为e对应状态2，er，r对应状态8，ers，rs，s对应状态9），然后分别将这些组中的子串从D0开始执行状态转移，直到没有可行的转移方案，或者整个序列使状态机最终转移到一个合法状态为止。如果一组中的所有子串都不能使状态机转移到一个合法状态，则这组子串所对应的状态的fail值为0，如果存在可行的状态转移方案，则选择其中最长的子串经过转移后的最终状态，令其对应的组的状态的fail值与其相等。举例说明，当我们要处理模式串hers的fail表，假设已经构建好的goto表如前图所示，首先我们需要考察状态2，此时hers的输入字符是he，其所有包含后缀只有e，我们让e从D0开始转移，发现成功转移到D10，所以fail2=10。然后我们考察状态8，此时hers的输入字符是her，所有包含后缀为er，r，因为我们要找到可以实现转移的最大包含后缀，所以我们先让er从D0开始转移，发现成功转移到D11，所以fail8=11，这是虽然后缀e也可以成功转移到D10，但是不是当前包含后缀分组中的子串所能实现的最长跳转，放弃。然后我们考察9，此时hers的输入字符串是hers，所有包含后缀为ers，rs，s，我们依次让其执行状态转换，发现s是可以实现转移的最长子串，转移到D3，所以fail9=3。下面给出构建fail表的代码:代码4.2 构建fail表void BuildFail(const vector& patterns)unsigned int t, m, last_state;unsigned int s20;vector:const_iterator vit;string:const_iterator sit1, sit2, sit3;for(vit = patterns.begin(); vit != patterns.end(); +vit)/*先要找到输入的单词的各字母对应的状态转移表的状态号，由于状态转移表没有*/记录各状态的前驱状态信息，该步暂时无法掠过t = 0;m = 0;sit1 = vit-begin();while(sit1 != vit-end() & _gotot*sit1 - a != 0)t = _gotot*sit1 - a;+sit1;sm+ = t;for(sit1 = vit-begin() + 1; sit1 != vit-end(); +sit1)/此时的sit2, sit1+1)就是当前模式的一个非前缀子串for(sit2 = vit-begin() + 1; sit2 != sit1 + 1; +sit2)t = 0;sit3 = sit2;/对该子串在goto表中执行状态转移while(sit3 != sit1 + 1 & _gotot*sit3 - a != 0)t = _gotot*sit3 - a;+sit3;/当前子串可以使goto表转移到一个非0位置if(sit3 = sit1 + 1)/求出输入当前子串在goto表中所转移到的位置last_state = ssit3-vit-begin() - 1;/*更新该位置的fail值，如果改为值得fail值为0，则用t值替换，因为对于sit1而言，是按照以其为末尾元素的非前缀*/*子串的由长到短的顺寻在goto表中寻找非0状态转移的，而满足条件的t是这里免得最长子串*/if(_faillast_state = 0)_faillast_state = t;/如果两者都标识完整的模式串if(_outlast_state.size() 0 & _outt.size() 0)/将outt内的模式串全部加入outlast_state中for(set:const_iterator cit = _outt.begin(); cit != _outt.end(); +cit)_outlast_state.insert(*cit);对于output表，在构建goto表的过程中，我们知道，状态2，5，7，9是输入的4个模式串的末尾部分，所以如果在执行匹配过程中，达到了如下四个状态，我们就知道对应的模式串被发现了。对于状态机D的某些状态，对应某个完整的模式串已经被发现，我们就用output表来记录这一信息。完成goto表的构建后，D中各状态对应的output表的情况如下：2 he5 she7 his9 hers但是这并不是我们最终的output表。下面以构建状态5的fail表为例，说明一下fail表的构建是如何影响output表的。首先根据之前我们的介绍，当我们开始计算D5的fail值时，我们要将模式she的所有包含后缀提取出来，包括he，e。这里我们需要注意，在output表中，状态5是一个输出状态。当我们用he在状态机中执行转移时，我们会成功转移到2，这里output2也是一个输出状态，这就意味着在发现模式串she的同时，实际上也发现了模式串he，所以如果通过某种转换，我们到达了状态5，则意味着我们发现了she和he两个模式，此时fail5=2，所以我们需要将output2所包含的输出字符串加入到output5中。完成goto和fail表构建后，我们所得到的最终output表为：2 he5 she，he7 his9 hers这实际上是一个后缀包含问题，也就是模式p1实际上是模式p2的后缀，所以当发现模式p2时，p1自然也被发现了。AC算法对文本进行匹配的具体步骤是。一开始，将i指向文本T1.j的起始位置，然后用Ti从goto表的状态D0开始执行状态跳转。如果存在可行的跳转方案D0Ti=p，p!=0，则将i增加1，同时转移到状态Dp。如果不存在可行的转移方案，则考察状态Dp的fail值，如果failp不等于0，则转移到Dfailp，再次查看DfailpTi是否等于0，直到发现不为0的状态转移方案或者对于所有经历过的fail状态，对于当前输入Ti都没有非0的转移方案为止，如果确实不存在非0的转移方案，则将i增加1，同时转移到D0继续执行跳转。在每次跳转到一个状态Dp时（fail跳转不算），都需要查看一下outputp是否指向可输出的模式串，如果有，说明当前位置匹配了某些模式串，将这些模