数据结构-KMP算法的实现

数据结构

课程设计报告设计题目：模式匹配中的KMP算法的实现专业：计算机科技院系：计算机学院姓名：xxxxxxxx学号：xxxxxxx时间：2013年9月22日1需求分析1.1问题描述1.2基本要求2概要设计3详细设计・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・3.1为主串和模式串赋值TOC\o"1-5"\h\z3.2利用Output()函数输出串。5,3.3求各串的长度3.4求模式串的模式值next[]函数3.5模式匹配KMP算法的实现：4测试与分析75总结96附录：源程序清单参考文献1需求分析1.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算法的最大特点是指示主串的指针不须回溯，整个匹配过程中，对主串仅需从头到尾扫描一遍，这对处理从外设输入的庞大文件很有效，可以边度入边匹配，而无需回头重读。开发工具：C语言1.2基本要求用C编写一个程序实现模式匹配的KMP算法。要求对于任何输入串入，实现算法求next函数值；利用next函数值，实现串A在串B中的定位；若未搜索到，就返回0。首先要从键盘输入主串B和模式串A，并采用用链式存储，再根据Next()函数求模式串的Next值，利用KMP算法进行匹配，再用输出函数输出结果！2概要设计对该kmp算法，定义的抽象数据类型如下：ADTString{数据对象：D={a.|a.ECharacterSet,i=1,2,3,…，n,n30}数据关系：R1={<ai-1,ai>|ai-1,ai£D,i=2,…,n}基本操作：StrAssign(&T,chars)初始条件：chars是字符串常量。操作结果：生成一个其值等于chars的串T。StrCopy(S)初始条件：串S存在。操作结果：若S为空串，则返回TRUE，否则返回FALSE0StrLength(S)初始条件：串S存在。操作结果：返回S元素的个数，成为串的长度。Index(S,T,pos)初始条件：串S和T存在，T是非空串，1WposWStrLength(S).操作结果：若主串S中存在和串T相同的子串，则返回他在主串S中的第pos个字符之后第一次出现的位置；否则函数值为0。DestoryString（&S）初始条件：串S存在。操作结果：串S被销毁。}ADTString该算法是对串进行操作，对串的存储结构用线性表的链式存储结构表示：typedefstructLString{chardata；structLString*next；}LString；该算法分为三个模块：第一模块［Input（）函数］（利用该函数输入主串和模式串）；第二模块［Output（）函数利用该函数输出串）。第三模块［Length（）］（利用该函数求各串的长度）；第四模块［Get_next（）函数］（利用该函数求出模式串的next函数值）；第五模块［Index_KMP（）函数］（利用该函数进行主串和模式串之间的匹配）；各个模块之间的调用关系如下图所示：图2.1是对整个函数的流程图。整个函数的流程图3详细设计：3.1为主串和模式串赋值利用Input()函数输入主串和模式串Input()函数伪代码：LString*Input()(〃通过标准输入设备输入串以链式存储存储数据并返回链的头指针。LString*head,*tail,*p;intcurlen=0;charch;head=(LString*)malloc(sizeof(LString));//建立头指针。if(!head)(printf(-存储分配失败")；exit(0);}〃存储分配失败。scanf("%c",&ch);while(ch!='\n'){p=(LString*)malloc(sizeof(LString));if(!p){printf(-存储分配失败")；exit(0);}//存储分配失败。p->data=ch;p->next=NULL;if(curlen==0)head->next=p;else{tail->next=p;}tail=p;++curlen;head->data=curlen;//用头指针存储串的长度scanf("%c",&ch);}returnhead;}//Inpute3.2利用Output()函数输出串。voidOutput(LString*T){〃在标准输出设备上输出串T。LString*p;p=T->next;while(p!=NULL){printf("%c",p->data);p=p->next;}printf("\n");}//Output3.3求各串的长度LengthO函数求的各串的长度，利用一个while循环语句，为后面的函数做好准备工作；intLength(LString*T)(〃求串T的长度并返回其值。intn=0;LString*head;head=T;if(head)n=head->data;returnn;}//Length3.4求模式串的模式值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+l]=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<k'<k<„<j)满足，此时若t1尹tj+1，则有：next[j+1]=1否则若t1=tj+1，则有：next[j+1]=0综上所述，求next函数值过程的伪码算法如下：voidGet_next(SStringT,intnext[])(〃求模式串T的next函数并存入数组next。i=1；next[1]=0;j=0;while(i<t[0]){if(j==0||t[i]==t[j]){++i;++j;next[i]=j;elsej=next[j];}}//Get_next3.5模式匹配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"=nsi-j+1si-j+2…si-1"(4.2)因为k<j，所以有："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分别增1，若si尹tj匹配失败后，则i不变，j退到next[j]位置再比较，若相等，则指针各自增1，否则j再退到下一个next值的位置，依此类推。直至下列两种情况：一种是j退到某个next值时字符比较相等，则i和j分别增1继续进行匹配；另一种是j退到值为零(即模式的第一个字符失配)，则此时i和j也要分别增1，表明从主串的下一个字符起和模式重新开始匹配。KMP算法如下：intIndex_KMP(SStringS,SStringT,intpos,intnext[])(//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的//KMP算法。其中，T非空。，1<pos<StrLength(S)i=pos;j=1;while(i<=S[0]&&j<=T[0])(if(j==0||s[i]==t[j])(//继续比较后继字符++i;++j;}elsej=next[j];//模式串向右移动}if(j>t[0])returni-t[0];//匹配成功elsereturn0;}//Index_KMP

4测试与分析4.1若匹配成功：调试结果如下图所示崩f人执行HHP算法的模式串H并WeHTER键结束:.aXlA崩f人执行HHP算法的模式串H并WeHTER键结束:.aXlA行州P算法主串B井以ENTEH链结束:王串:abcdefy输入执行H*算法从主串开始的位置并以邸T国键结束:■!匹配结果如下，匹配结果枷执行旭虹函数的值E&模式串在主串的第］位置；aJbcdefgabed__匹配成功'rcss讥nykeytocontinvc图4.1"匹配不成功：调试结果如下所示©必做耙4：KMP算法@姓名：杨建学号：EB1114299疽I制行"P算法的模式串A并Renter键结束:模式串:abcl23、辄A执行KMP算法主串B并以ENTER键结束二主串:abedefghijklmn输入执行KMP算法从主串开始的位置并以ENTER键结耘pos=l匹配结果如下:匹配结果匹配失败对计执行Next函数的值，011111匹配失败Pressanykeytocontinue图4.2匹配失败£5总结通过此次模式匹配中的KMP算法的实现的课设，我认识到自己在以前的课程学习中还有很多的不足。在课设中，我了解到各种算法对软件设计的重要性，它能帮助程序设计者设计出更好的程序为人们的日常生活提供了更大的帮助。本次课设在平时的字符的查找中发挥了重要作用。这次课设让我对C语言又复习了一遍。6附录：源程序清单#include<stdio.h>#include<string.h>#include<stdlib.h>typedefstructLString{〃串的链式存储表示。chardata;structLString*next;}LString;LString*Input(){〃通过标准输入设备输入串以链式存储存储数据并返回链的头指针。LString*head,*tail,*p;intcurlen=0;charch;head=(LString*)malloc(sizeof(LString));//建立头指针。if(!head){printf(-存储分配失败")；exit(0);}//存储分配失败。scanf("%c",&ch);while(ch!='\n'){p=(LString*)malloc(sizeof(LString));if(!p){printf(-存储分配失败")；exit(0);}//存储分配失败。p->data=ch;p->next=NULL;if(curlen==0)head->next=p;else{tail->next=p;}tail=p;++curlen;head->data=curlen;//用头指针存储串的长度scanf("%c",&ch);}returnhead;}//InputevoidOutput(LString*T)(〃在标准输出设备上输出串T。LString*p;p=T->next;while(p!=NULL){printf("%c",p->data);p=p->next;}printf("\n");}//OutputintLength(LString*T){〃求串T的长度并返回其值。intn=0;LString*head;head=T;if(head)n=head->data;returnn;}//LengthvoidGet_next(LString*T,intnext[]){〃求模式串T的next函数并存入数组nextointi=1;intj=0;intk;chart[100];LString*p;p=T;for(k=0;k<=Length(T);k++)//将串丁的链式存储转换为顺序存储并存入数组t。{t[k]=p->data;p=p->next;}next[1]=0;while(i<t[0]){if(j==0||t[i]==t[j])++i;++j;next[i]=j;}elsej=next[j];}next[i+1]='\n';}//Get_nextintIndex_KMP(LString*S,LString*T,intpos,intnext[]){//利用模式串T的next函数求丁在主串S中第pos个字符之后的位置的//KMP算法。其中，T非空。，1<pos<StrLength(S)inti=pos;intj=1;intk;LString*p,*q;chars[255],t[255];p=S;q=T;for(k=0;k<=Length(S);k++)//将串、的链式存储转换为顺序存储{s[k]=p->data;p=p->next;}for(k=0;k<=Length(T);k++)//将串丁的链式存储转换为顺序存储{t[k]=q->data;q=q->next;}while(i<=Length(S)&&j<=Length(T)){if(j==0||s[i]==t[j]){//继续比较后继字符++i;++j;}elsej=next[j];//模式串向右移动}if(j>t[0])returni-t[0];//匹配成功elsereturn0;}//Index_KMPvoidmain(){system("cls");system("color1f");system("modecon:cols=78lines=35");TOC\o"1-5"\h\zprintf(-|1\n");printf("|㊣必做题4：KMP算法㊣|\n");printf("|姓名:xxxx|\n");printf("|学号：xxxxxxxxxx|\n");printf("11\n");intLoc,Next[255],pos=0,i=1,j=1;LString*A,*B;printfC输入执行KMP算法的模式串A并以ENTER键结束:\n模式串:")；A=Input();//从标准输入设备接收模式串。