模式匹配KMP算法研究报告.docx

模式匹配KMP算法研究报告.docx

《模式匹配KMP算法研究报告.docx》由会员分享，可在线阅读，更多相关《模式匹配KMP算法研究报告.docx（14页珍藏版）》请在冰点文库上搜索。

模式匹配KMP算法研究报告

模式匹配的KMP算法研究

学生姓名：

黄飞指导老师：

罗心

摘要在计算机科学领域，串的模式匹配<以下简称为串匹配）算法一直都是研究焦点之一。

在拼写检查、语言翻译、数据压缩、搜索引擎、网络入侵检测、计算机病毒特征码匹配以及DNA序列匹配等应用中，都需要进行串匹配。

串匹配就是在主串中查找模式串的一个或所有出现。

在本文中主串表示为S=s1s2s3…sn，模式串表示为T=t1t2…tm。

串匹配从方式上可分为精确匹配、模糊匹配、并行匹配等，著名的匹配算法有BF算法、KMP算法、BM算法及一些改进算法。

本文主要在精确匹配方面对KMP算法进行了讨论并对它做一些改进以及利用改进的KMP来实现多次模式匹配。

关键字：

模式匹配；主串；模式串；KMP算法

ResearchandAnalysisofKMPPatternMatchingAlgorithm

Student:

HuangfeiTeacher:

Luoxin

AbstractIncomputerscience,Stringpatternmatching（Hereinafterreferredtoasthestringmatching>algorithmisalwaysthefocusofthestudy.Inthespellcheck,languagetranslation,datacompression,searchengine,thenetworkintrusiondetectionsystem,acomputervirussignaturematchingDNAsequencesandtheapplicationinthematch,matchedtostringmatching.Stringmatchingisinsearchofastringofpatternorallappear.Inthispaper,thestringisS=s1s2s3...Sn,stringpatternforT=t1t2...tm.Stringmatchingwaycanbedividedfromtheaccuratematching,fuzzymatching,parallelmatchingetc.,thefamousmatchingalgorithmsareKMPalgorithm,BFalgorithm,thealgorithmandsomeBMalgorithm.ThispaperinpreciseKMPalgorithmformatchingaspectsarediscussedandsomeimprovementonitandusingtheimprovedKMPtorealizethemultiplepatternmatching.

Keywords:

patternmatching,Thestring。

Patternstrings。

KMPalgorithm

1引言

KMP算法是是对一般模式匹配算法的改进，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的因此人们称它为克努特-莫里斯-莫拉特操作<简称为KMP算法）。

对于一般的模式匹配算法：

分别利用两个指针i和j指示主串S和T中的当前正待比较的字符位置。

算法的基本思想是：

从主串的S的第POS个字符开始起和模式的第一个字符比较之，如相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较之。

以此类推，直到模式T中的每个字符依次和主串S中的一个连续字符序列相等，则称匹配成功，则函数值为和模式T中的第一个字符相等的字符在主串S中的序号，否则称匹配不成功，函数值为0.而对于模式匹配的KMP算法可以在O（n+m>的时间数量级上完成串的模式匹配操作。

其改进过程在于:

每当一趟匹配过程出现字符比较不相等时，不需回溯i指针，而是利用已经得到的部分匹配的结果将模式串向右滑动一段尽可能远的距离后，继续进行比较。

滑动的这一段距离我们将会用到函数next[],

KMP算法的最大特点是指示主串的指针不须回溯，整个匹配过程中，对主串仅需从头到尾扫描一遍，这对处理从外设输入的庞大文件很有效，可以边度入边匹配，而无需回头重读。

2、问题分析

2.1问题的分析和任务的定义

用C/C++编写一个程序实现模式匹配的KMP算法。

要求在一个字符串中搜索某个子串，若搜索到就返回子串的位置；若未搜索到，就返回0。

首先要输入个主串和模式串，先根据next（>函数求模式串的next值，利用KMP算法进行匹配，再用输出函数输出结果！

2.2设计过程

本次课程设计利用模式匹配KMP算法实现串的相关操作：

分别从键盘上任意输入三组字符串作为主串，在任意数取三组字符串作为模式串，利用《模式匹配KMP算法》依次使三组模式串与三组主串匹配，在使用《模式匹配KMP算法》时会调用到Getnext（>函数。

2.3逻辑设计

对该kmp算法，定义的抽象数据类型如下：

ADTString{

数据对象：

D={ai|ai∈CharacterSet,i=1,2,3,…,n,n≥0}

数据关系：

R1={|ai-1,ai∈D,i=2,…,n}

基本操作：

StrAssign（&T,chars>

初始条件：

chars是字符串常量。

操作结果：

生成一个其值等于chars的串T。

StrCopy

初始条件：

串S存在。

操作结果：

若S为空串，则返回TRUE，否则返回FALSE。

StrLength（S>

初始条件：

串S存在。

操作结果：

返回S元素的个数，成为串的长度。

Index（S,T,pos>

初始条件：

串S和T存在，T是非空串，1≤pos≤StrLength（S>.

操作结果：

若主串S中存在和串T相同的子串，则返回他在主串S中的第pos个字符之后第一次出现的位置；否则函数值为0。

DestoryString（&S>

初始条件：

串S存在。

操作结果：

串S被销毁。

}ADTString

该算法是对进行操作，对串的存储结构用—定长顺序存储表示：

类似于现性表的顺序存储结构，用一组地址连续的存储单元存储串值得字符序列。

在串的定长顺序存储结构中，按照与定义大小，为每个定义的串分配一个固定长度的存储区，则可用定长数组如下描述。

#defineMAXSTRLEN255

typedefunsignedcharSString[MAXSTRLEN+1]

该算法分为五三个模块：

第一模块[StrLength<）]<利用该函数求各串的长度）；第二模块[input（>函数]<利用该函数输入主串和模式串的值）；第三模块[get_next（>函数]<利用该函数求出模式串的next函数值）；第四模块[Index_KM<）函数]<利用该函数进行主串和模式串之间的匹配）；第五模块[output（>函数利用该函数输出匹配结果）。

个模块之间的调用关系如下图所示：

图4.1是对整个函数的流程图。

图4.2是对KMP算法的流程图；图4.3是求next的函数值的流程图。

图2.1模块调用流程图

3、解决方案

3.1为主串和模式串赋值

分别定义三组字符串作为主串str1,str2,str3,利用cin函数依次为为三组字符串赋值，从键盘上任意输入字符分别赋给str1str2str3,。

以同样的方法模模式串p1,p2,p3赋值。

3.2求各串的长度

StrLength<）函数求的各串的长度，利用一个while循环语句，为后面的函数做好准备工作。

3.3求模式串的模式值next[]函数

用《模式匹配的KMP算法》当主串和模式串匹配不相等是，模式串应向右移动一段距离，此时我们需要得到模式串的next函数值。

如何求next函数，next函数值仅取决于模式本身而和主串无关。

我们可以从分析next函数的定义出发用递推的方法求得next函数值。

由定义知：

next[1]=0设next[j]=k，即有：

＂t1t2…tk-1＂=＂tj-k+1tj-k+2…tj-1next[j+1]=?

　可能有两种情况：

一种情况：

若tk＝tj则表明在模式串中这就是说next[j+1]=k+1，即next[j＋１]=next[j]+1第二种情况：

若tk≠tj则表明在模式串中t1t2…tk＂≠＂tj-k+1tj-k+2…tj＂此时可把求next函数值的问题看成是一个模式匹配问题，整个模式串既是主串又是模式，而当前在匹配的过程中，已有（4.6>式成立，则当tk≠tj时应将模式向右滑动，使得第next[k]个字符和“主串”中的第j个字符相比较。

若next[k]=k′，且tk′＝tj，则说明在主串中第j+1个字符之前存在一个最大长度为k′的子串，使得＂t1t2…tk′＂=＂tj-k′+1tj-k′+2…tj＂此：

next[j+1]=next[k]+1

同理若tk′≠tj，则将模式继续向右滑动至使第next[k′]个字符和tj对齐，依此类推，直至tj和模式中的某个字符匹配成功或者不存在任何k′（1满足，此时若t1≠tj+1，则有：

next[j+1]=1否则若t1=tj+1，则有：

next[j+1]=0

综上所述，求next函数值过程的算法如下：

voidget_next（chart,intnext[]>

/*求模式t的next值并寸入next数组中*/

｛　inti=1,j=0。

next[0]=0。

while（i

{while（j==0||t[i-1]==t[j-1]>{++i。

++j。

next[i-1]=j。

}。

elsej=next[j-1]。

}

}//get_next

3.4模式匹配KMP算法的实现

KMP算法的思想：

主串s，模式t希望某趟在si和tj匹配失败后，指针i不回溯，模式t向右“滑动”至某个位置上，使得tk对准si继续向右进行。

显然，现在问题的关键是串t“滑动”到哪个位置上？

不妨设位置为k，即si和tj匹配失败后，指针i不动，模式t向右“滑动”，使tk和si对准继续向右进行比较，要满足这一假设，就要有如下关系成立：

＂t1t2…tk-1＂=＂si-k+1si-k+2…si-1＂（4.1>式左边是tk前面的k-1个字符，右边是si前面的k-1个字符。

而本趟匹配失败是在si和tj之处，已经得到的部分匹配结果是：

＂t1t2…tj-1＂=＂si-j+1si-j+2…　si-1＂<4.2）因为k

＂tj-k+1tj-k+2…tj-1＂=＂si-k+1si-k+2…　si-1＂（4.3>式左边是tj前面的k-1个字符，右边是si前面的k-1个字符，通过（4.1>和（4.3>得到关系：

＂t1t2…tk-1＂=＂tj-k+1tj-k+2…tj-1＂（4.4>结论：

某趟在si和tj匹配失败后，如果模式串中有满足关系（4>的子串存在，即：

模式中的前k-1个字符与模式中tj字符前面的k-1个字符相等时，模式t就可以向右“滑动”至使tk和si对准，继续向右进行比较即可。

在求得模式的next函数之后，匹配可如下进行：

假设以指针i和j分别指示主串和模式中的比较字符，令i的初值为pos，j的初值为1。

若在匹配过程中si≠tj，则i和j分别增１，若si≠tj匹配失败后，则i不变，j退到next[j]位置再比较，若相等，则指针各自增１，否则j再退到下一个next值的位置，依此类推。

直至下列两种情况：

一种是j退到某个next值时字符比较相等，则i和j分别增１继续进行匹配。

另一种是j退到值为零<即模式的第一个字符失配），则此时i和j也要分别增１，表明从主串的下一个字符起和模式重新开始匹配。

KMP算法如下：

intStrIndex_KMP（char*s,char*t,intpos>

　　/*从串s的第pos个字符开始找首次与串t相等的子串*/

{inti=pos,j=-1,slen,tlen。

while（i<=s[0]&&j<=t[0]>/*都没遇到结束符*/

if（j==-1||s==t[j]>{i++。

j++。

}

elsej=next[j]-1。

/*回溯*/

if（j>t[0]>returni-t[0]+1。

/*匹配成功，返回存储位置*/

elsereturn0

}

4程序调试与测试

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

对于next（>函数的时间复杂度为O

5结束语

在这次课程设计中，我做的一个简单的模式匹配的kmp的算法，该算法是对一般算法的改进，kmp算法仅当模式与主串之间存在部分匹配时才比一般模式匹配算法快。

其次该算法的最大特点是，指示主串的指针不需回溯，整个匹配过程中，对主串仅需要从头到尾扫描一遍，这时处理从外设输入的庞大文件有很大的效果，可以边输入边匹配，而无需回头读。

刚开始，对求子串的next[]值时，我仅对一串字符进行实例说明，经过自己和组员的讨论，我们共同研究才开始理解了该算法的应用，。

让我们体验到了“过程是完美的”；正如一句话所说的，“我们可以错过一路风景，但不能错过终点站”我将之改为“我可以不在乎结果，但我们永远记得过程最美”。

一个好的程序=好结构+好结构，这次课设真让我体验到这句话。

当然，通过这次课程设计，我也发现了自身的很多不足之处，在以后的学习中，我会不断的完善自我，不断进取，能使自己在编程这方面有一个大的发展。

在以后的工作中，我会弥补自己在设计方面的不足。

在工作中，学会合作。

其次，谢谢老师，学校给我提供的这次机会！

参考文献

[1]严蔚敏吴伟民《数据结构》

[2]王宏生宋继红《数据结构》北京.国防工业出版社.2006

[3]彭波《数据结构教程》北京.清华出版社.2004

[4]谭浩强《c++程序设计》北京.清华大学出版社.2008

[5]陈杰《计算机专业课程设计中的需求分析[J]》集美大学学报.2009

[6]高一凡《数据结构算法实现及解读[M]》西安.西安电子科技大学出版社.2002

[7]黄国瑜叶乃箐《数据结构》

附录：

程序清单

#include"iostream.h"

#include"string"

#include"stdlib.h"

#defineMaxStrLen200

char

s1[MaxStrLen],s2[MaxStrLen],s3[MaxStrLen],p1[20],p2[20],p3[20]。

intnext[20]。

intStrLength（char*s>。

voidinput（>。

intIndex_KMP（char*s,char*t,intpos,intnext[]>。

voidget_next（char*s,intnext[]>。

voidoutput（>。

intStrLength（char*s>

{

inti,len。

i=0。

len=0。

while（s[i]!

='\0'>{len+=1。

i++。

}

returnlen。

}

voidinput（>

{//利用该函数为串赋值。

cout<<"pleaseinputthemainstringofS1:

\n"。

cin>>s1。

cout<<"pleaseinputthemainstringofS2:

\n"。

cin>>s2。

cout<<"pleaseinputthemainstringofS3:

\n"。

cin>>s3。

cout<<"pleaseinputthesubstringofp1:

\n"。

cin>>p1。

cout<<"pleaseinputthesubstringofp2:

\n"。

cin>>p2。

cout<<"pleaseinputthesubstringofp3:

\n"。

cin>>p3。

}

intIndex_KMP（char*s,char*t,intpos,intnext[]>

{//利用模式t的next函数求主串s中的第pos个字符后的位置。

//串s和t采用定长顺序存储,且t非空,1<=pos<=strlent（s>-strlent（t>+1.

inti,j,ls,lt。

i=pos-1,j=-1。

//设置初值

ls=StrLength（s>。

//求主串s的长度

lt=StrLength（t>。

//求模式串t的长度

while（i{

if（j==-1||s[i]==t[j]>{//继续比较后继字符

i++。

j++。

}

else{

j=next[j]-1。

//模式串向右移

}

}

if（j>=lt>returni-lt+1。

//匹配成功

elsereturn0。

//匹配不成功

}

voidget_next（char*s,intnext[]>

{//求模式串的next函数值并存入数组next,为后面进行模式匹配做准备

inti,j。

i=1。

j=0。

//设置初值

next[0]=0。

while（i>

{

if（j==0||s[i-1]==s[j-1]>//若j==0或s[i-1]=s[j-1],令next[i]=j+1.

{

i++。

j++。

next[i-1]=j。

}

else

j=next[j-1]。

//若j!

=0或s[i-1]!

=s[j-1],令j=next[j-1]

}

cout<<"next="<<'\t'。

for（i=0。

i。

i++>

cout<

cout<

}

voidoutput（>

{cout<<"子串p1在主串s1的"<<<"相匹配"<<'\n'。

cout<<"子串p2在主串s2的"<<<"相匹配"<<'\n'。

cout<<"子串p3在主串s3的"<<<"相匹配"<<'\n'。

}

voidmain（>

{

input（>。

get_next（p1,next>。

get_next（p2,next>。

get_next（p3,next>。

cout<

output（>。

}