模式匹配的KMP算法研究

1、模式匹配的KMP算法研究学生姓名：黄飞 指导老师：罗心摘 要 在计算机科学领域，串的模式匹配（以下简称为串匹配）算法一直都是研究焦点之一。在拼写检查、语言翻译、数据压缩、搜索引擎、网络入侵检测、计算机病毒特征码匹配以及DNA序列匹配等应用中，都需要进行串匹配。串匹配就是在主串中查找模式串的一个或所有出现。在本文中主串表示为S=s1s2s3sn，模式串表示为T=t1t2tm。串匹配从方式上可分为精确匹配、模糊匹配、并行匹配等，著名的匹配算法有BF算法、KMP算法、BM算法及一些改进算法。本文主要在精确匹配方面对KMP算法进行了讨论并对它做一些改进以及利用改进的KMP来实现多次模式匹配。 关键字：

2、模式匹配；主串；模式串；KMP算法 Research and Analysis of KMP Pattern Matching AlgorithmStudent:Huangfei Teacher:Luoxin Abstract In computer science, String pattern matching(Hereinafter referred to as the string matching) algorithm is always the focus of the study. In the spell check, language translation, data co

3、mpression, search engine, the network intrusion detection system, a computer virus signature matching DNA sequences and the application in the match, matched to string matching. String matching is in search of a string of pattern or all appear. In this paper, the string is S = s1s2s3. Sn, string pat

4、tern for T = t1t2. tm. String matching way can be divided from the accurate matching, fuzzy matching, parallel matching etc., the famous matching algorithms are KMP algorithm, BF algorithm, the algorithm and some BM algorithm. This paper in precise KMP algorithm for matching aspects are discussed an

5、d some improvement on it and using the improved KMP to realize the multiple pattern matching.Key words: pattern matching, The string; Pattern strings;KMP algorithm1 引言KMP算法是是对一般模式匹配算法的改进，由D.E.Knuth与V.R.Pratt和J.H.Morris 同时发现的因此人们称它为克努特-莫里斯-莫拉特操作（简称为KMP算法）。对于一般的模式匹配算法：分别利用两个指针i和j指示主串S和T中的当前正待比较的字符位置。算

6、法的基本思想是：从主串的S的第POS个字符开始起和模式的第一个字符比较之，如相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较之。以此类推，直到模式T中的每个字符依次和主串S中的一个连续字符序列相等，则称匹配成功，则函数值为和模式T中的第一个字符相等的字符在主串S中的序号，否则称匹配不成功，函数值为0.而对于模式匹配的KMP算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。其改进过程在于:每当一趟匹配过程出现字符比较不相等时，不需回溯i指针，而是利用已经得到的部分匹配的结果将模式串向右滑动一段尽可能远的距离后，继续进行比较。滑动的这一段距离我们将会用到函数ne

7、xt, KMP算法的最大特点是指示主串的指针不须回溯，整个匹配过程中，对主串仅需从头到尾扫描一遍，这对处理从外设输入的庞大文件很有效，可以边度入边匹配，而无需回头重读。2、问题分析2.1 问题的分析和任务的定义用C/C+编写一个程序实现模式匹配的KMP算法。要求在一个字符串中搜索某个子串，若搜索到就返回子串的位置；若未搜索到，就返回0。 首先要输入个主串和模式串，先根据next( )函数求模式串的next值，利用KMP 算法进行匹配，再用输出函数输出结果！2.2 设计过程本次课程设计利用模式匹配KMP算法实现串的相关操作：分别从键盘上任意输入三组字符串作为主串，在任意数取三组字符串作为模式串，

8、利用模式匹配KMP算法依次使三组模式串与三组主串匹配，在使用模式匹配KMP算法时会调用到Getnext()函数。2.3 逻辑设计对该kmp 算法，定义的抽象数据类型如下：ADT String 数据对象：D=ai|aiCharacterSet,i=1,2,3,n,n0 数据关系：R1=<ai-1,ai>|ai-1,aiD,i=2,n 基本操作：StrAssign(&T,chars) 初始条件：chars是字符串常量。操作结果：生成一个其值等于chars的串T。 StrCopy（S）初始条件：串S存在。操作结果：若S为空串，则返回TRUE，否则返回FALSE。 StrLengt

9、h(S)初始条件：串S存在。操作结果：返回S元素的个数，成为串的长度。 Index(S,T,pos)初始条件：串S和T存在，T是非空串，1posStrLength(S).操作结果：若主串S中存在和串T相同的子串，则返回他在主串S中的第pos个字符之后第一次出现的位置；否则函数值为0。 DestoryString(&S)初始条件：串S存在。操作结果：串S被销毁。ADT String 该算法是对进行操作，对串的存储结构用定长顺序存储表示：类似于现性表的顺序存储结构，用一组地址连续的存储单元存储串值得字符序列。在串的定长顺序存储结构中，按照与定义大小，为每个定义的串分配一个固定长度的存储区，

10、则可用定长数组如下描述。 #define MAXSTRLEN 255typedef unsigned char SStringMAXSTRLEN+1该算法分为五三个模块：第一模块StrLength（）（利用该函数求各串的长度）；第二模块input( )函数（利用该函数输入主串和模式串的值）；第三模块get_next( )函数（利用该函数求出模式串的next函数值）；第四模块Index_KM（）函数（利用该函数进行主串和模式串之间的匹配）；第五模块output( )函数利用该函数输出匹配结果）。个模块之间的调用关系如下图所示：图4.1是对整个函数的流程图。图4.2是对KMP算法的流程图；图4.3

11、是求next的函数值的流程图。图2.1模块调用流程图3、解决方案3.1 为主串和模式串赋值分别定义三组字符串作为主串str1,str2,str3,利用cin函数依次为为三组字符串赋值，从键盘上任意输入字符分别赋给str1 str2 str3,;以同样的方法模模式串p1,p2,p3赋值。3.2 求各串的长度StrLength（）函数求的各串的长度，利用一个while循环语句，为后面的函数做好准备工作。3.3 求模式串的模式值next函数用模式匹配的KMP算法当主串和模式串匹配不相等是，模式串应向右移动一段距离，此时我们需要得到模式串的next函数值。 如何求next函数，next函数值仅取决于模

12、式本身而和主串无关。我们可以从分析next函数的定义出发用递推的方法求得next函数值。由定义知：next1=0设nextj=k，即有：t1 t2 tk-1 =tj-k+1 tj-k+2 tj-1 nextj+1=?可能有两种情况：一种情况：若tk tj 则表明在模式串中这就是说nextj+1=k+1，即nextj=nextj+1 第二种情况：若tk tj 则表明在模式串中t1 t2 tk tj-k+1 tj-k+2 tj 此时可把求next函数值的问题看成是一个模式匹配问题，整个模式串既是主串又是模式，而当前在匹配的过程中，已有(4.6)式成立，则当tk tj 时应将模式向右滑动，使得第ne

13、xtk个字符和“主串”中的第j个字符相比较。若nextk=k，且t ktj，则说明在主串中第j+1个字符之前存在一个最大长度为k的子串，使得t1 t2 t k =tj-k+1 tj- k+2 tj 此： nextj+1=nextk+1 同理若t k tj，则将模式继续向右滑动至使第nextk个字符和tj 对齐，依此类推，直至tj 和模式中的某个字符匹配成功或者不存在任何 k(1< k<k <<j)满足，此时若t1tj+1 ， 则有：nextj+1=1 否则若t1=tj+1 ，则有：nextj+1=0 综上所述，求next函数值过程的算法如下：void get _next

14、(char t,int next )/*求模式t的next值并寸入next数组中*/ int i=1,j=0;next0=0;while (i<t0) while (j=0|ti-1 = =tj-1) +i;+j;nexti-1=j; else j=nextj-1;/get_next3.4 模式匹配KMP算法的实现KMP算法的思想：主串s，模式t希望某趟在si和tj匹配失败后，指针i不回溯，模式t向右“滑动”至某个位置上，使得tk 对准 s i 继续向右进行。显然，现在问题的关键是串t“滑动”到哪个位置上？不妨设位置为k，即si和tj匹配失败后，指针i不动，模式t向右“滑动”，使tk和s

15、i对准继续向右进行比较，要满足这一假设，就要有如下关系成立：t1 t2 tk-1 =si-k+1 si-k+2 si-1 (4.1)式左边是tk前面的k-1个字符，右边是si 前面的k-1个字符。而本趟匹配失败是在si和tj之处，已经得到的部分匹配结果是：t1 t2 tj-1 =si-j+1 si-j+2 si-1 （4.2）因为k<j，所以有：tj-k+1 tj-k+2 tj-1 =si-k+1 si-k+2 si-1 (4.3)式左边是 tj前面的k-1个字符，右边是si 前面的k-1个字符，通过(4.1)和(4.3)得到关系：t1 t2 tk-1 =tj-k+1 tj-k+2 tj

16、-1 (4.4)结论：某趟在si和tj匹配失败后，如果模式串中有满足关系(4)的子串存在，即：模式中的前k-1个字符与模式中tj字符前面的k-1个字符相等时，模式t就可以向右“滑动”至使tk和si对准，继续向右进行比较即可。在求得模式的next函数之后，匹配可如下进行：假设以指针i和j分别指示主串和模式中的比较字符，令i的初值为pos，j的初值为1。若在匹配过程中sitj，则i和j分别增，若sitj 匹配失败后，则i不变，j退到nextj位置再比较，若相等，则指针各自增，否则j再退到下一个next值的位置，依此类推。直至下列两种情况：一种是j退到某个next值时字符比较相等，则i和j分别增继续

17、进行匹配; 另一种是j退到值为零（即模式的第一个字符失配），则此时i和j也要分别增，表明从主串的下一个字符起和模式重新开始匹配。KMP算法如下：int StrIndex_KMP(char *s,char *t,int pos)/*从串s的第pos个字符开始找首次与串t相等的子串*/ int i=pos,j=-1,slen,tlen;while (i<=s0 && j<=t0 ) /*都没遇到结束符*/if (j=-1|s=tj) i+; j+; else j=nextj-1; /*回溯*/if (j>t0) return i-t0+1;/*匹配成功，返回存储位

18、置*/else return 04程序调试与测试4.1 若匹配成功：调试结果如下图所示图4.1 匹配成功4.2 若匹配不成功：调试结果如下所示图4.2 匹配不成功4.3 结果分析利用该程序求模式串是否可以在主串中找到，先利用next( )函数求的模式串的next 函数值，利用for 循环语句分别输出next 函数值：（0，1，2，3，4）；（0，1，2，3）（0，1，1，2，2，3，1，2），再用KMP算法进行查找，若查找成功则输出模式串在主串中的位置:9 ,8, 9. 若没有找到则返回0；该调试结果与程序相对应；对于模式匹配KMP算法时间复杂度为O（n+m）;对于next( )函数的时间复杂

19、度为O（m）其中n表示主串的长度，m表示子串的长度。5 结束语在这次课程设计中，我做的一个简单的模式匹配的kmp的算法，该算法是对一般算法的改进，kmp算法仅当模式与主串之间存在部分匹配时才比一般模式匹配算法快。其次该算法的最大特点是，指示主串的指针不需回溯，整个匹配过程中，对主串仅需要从头到尾扫描一遍，这时处理从外设输入的庞大文件有很大的效果，可以边输入边匹配，而无需回头读。 刚开始，对求子串的next值时，我仅对一串字符进行实例说明，经过自己和组员的讨论，我们共同研究才开始理解了该算法的应用，。让我们体验到了“过程是完美的”；正如 一句话所说的，“我们可以 错过一路风景，但不能错过终点站”

20、我将之改为“我可以不在乎结果，但我们永远记得过程最美”。一个好的程序=好结构+好结构，这次课设真让我体验到这句话。当然，通过这次课程设计，我也发现了自身的很多不足之处，在以后的学习中，我会不断的完善自我，不断进取，能使自己在编程这方面有一个大的发展。在以后的工作中，我会弥补自己在设计方面的不足。在工作中，学会合作。其次，谢谢老师，学校给我提供的这次机会！参考文献1 严蔚敏 吴伟民数据结构（c语言版）北京.清华出版社.20082 王宏生 宋继红数据结构北京.国防工业出版社.20063 彭波数据结构教程北京.清华出版社.20044 谭浩强c+程序设计北京.清华大学出版社.20085 陈杰计算机专业

21、课程设计中的需求分析J集美大学学报.20096 高一凡数据结构算法实现及解析M 西安.西安电子科技大学出版社. 20027 黄国瑜 叶乃箐数据结构（c语言版）北京.清华大学出版社.2001附录： 程序清单# include"iostream.h"# include "string"# include"stdlib.h"#define MaxStrLen 200char s1MaxStrLen,s2MaxStrLen,s3MaxStrLen,p120,p220,p320;int next20;int StrLength(char* s)

22、;void input();int Index_KMP(char* s,char* t,int pos,int next);void get_next(char* s,int next);void output();int StrLength(char* s)int i,len;i=0;len=0;while(si!='0') len+=1;i+;return len;void input() /利用该函数为串赋值。cout<<"please input the main string of S1:n"cin>>s1;cout<

23、<"please input the main string of S2:n"cin>>s2;cout<<"please input the main string of S3:n"cin>>s3;cout<<"please input the sub string of p1:n"cin>>p1;cout<<"please input the sub string of p2:n"cin>>p2;cout<<&q

24、uot;please input the sub string of p3:n"cin>>p3; int Index_KMP(char* s,char* t,int pos,int next)/利用模式t的next函数求主串 s中的第pos个字符后的位置;/串s和t采用定长顺序存储,且t非空,1<=pos<=strlent(s)-strlent(t)+1.int i,j,ls,lt;i=pos-1,j=-1;/设置初值ls=StrLength(s); /求主串s的长度lt=StrLength(t);/求模式串t的长度while(i<ls && j<lt) if(j=-1 | si=tj) /继续比较后继字符 i+; j+; else j=nextj-1; /模式串向右移 if (j>=lt) return i-lt+1;/匹配成功else return 0