KMP算法_实验报告

1西安交通大学实验报告课程数据结构实验名称基于串的模式匹配第1页共页系别__自动化实验日期/2014年11月15日专业班级自动化43班实验报告日期2014年11月22日姓名李欣阳学号2140504066报告退发(订正、重做)同组人无教师审批签字一、实验目的熟练掌握串的运用，以及线性表、栈、队列等的基本操作；理解KMP模式匹配算法的原理，能够利用该算法解决实际问题。二、实验内容与要求1.自由选择一个C程序文件作为程序的输入；2.通过键盘输入待查找的模式串，求取并显示next数组；3.判断该程序代码中是否包含该模式串，如果包含，输出左右该模式串在程序代码中文件中的位置（包括行数和该行的第几个字符）；4.用KMP算法进行实现。三、问题分析3.1KMP算法综述KMP算法是一个非常优秀的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，其时间复杂度为O（m+n）。该算法相对于普通匹配算法的改进在于：每当一趟匹配过程中出现字符比较不等时，不许回溯指针i，而是利用已经得到的部分匹配的结果将模式向右滑动尽可能远的一段距离后，继续进行比较。3.2next数组的计算正确求得next数组是实现KMP算法的关键，它决定了在匹配过程中出现字符不等时，模式串应该向右滑动的距离。next数组定义如下：，其他情况，当此集合非空时且时，当1'...''...'jk1|kax1j0][next1111jkjkppppMj求得next数组后，匹配按照如下方式进行：假设指针i和j分别指示主串和2模式串中正待比较的字符，令i初值为pos，j的初值为1，若在匹配过程中对应位置字符相等，则i和j增1；如果出现不相等的情况，则j退到next[j]的位置继续进行比较。3.3一行多次匹配的实现由于原始的KMP算法在完成一次模式匹配后会推出算法，想要实现一行多个的模式匹配，需要设计结构存储每一行模式匹配中，模式串出现的位置。因此定义数组linepos[20]来存储模式串在每一行出现的位置。具体实现方法是：在进行模式匹配是，如果在主串中出现与模式相匹配的连续串，则把该串在主串中出现的位置记录到linpos数组中，此后i不归零而是继续进行匹配，知道主串中的每个字符都与模式串比较过。这样逐行重复上述算法就可以实现每一行的多次匹配。3.4C程序文件的读入算法要求能对C程序代码文件进行模式匹配，在解决单行模式匹配问题后，需要解决的就是C程序文件的读入。在读入程序文件时有两种方式，一是整体读入文件后分行存储，另一个是分行读取，为了节省内存空间优化算法，本算法采用分行读取分行匹配的方式。文件的读取需要借助C语言文件打开函数fopen，在读取文件文件后，以’\n’作为行与行之间的分隔符，借助fgets等函数实现C程序文件的分行读取。分行读取完成后借助单行匹配函数即可实现全文的模式匹配。四、相关数据结构及基本操作4.1顺序串结构体的定义本算法需要用到串结构，顺序串适用一组连续的存储单元存储串值得字符序列，在串的定长顺序结构中，按照预定义的大小为每个定义的串变量分配一个固定长度的存储区，串的实际长度可以在这预定义长度内随意变动，超过预定义长度则会被舍去。结构体成员包括字符数组和数组长度，顺序串的结构体C语言定义如下：typedefstructseqstring{charstring[MAX_LINE];intlength;}seqstring4.2串的基本操作串的基本操作函数包含在标准函数库string.h中，包括求串长Strlen、串赋值StrAssign、串连接Concat、串比较StrCompare、求字串SubString等，已经能够满足本算法需求，不需要重新定义新的操作函数。五、算法设计3为了实现算法功能，并满足结果动态演示的需求，该算法的基本部分应该包括以下几个模块：（1）串的结构体定义（2）求next数组的函数getnext主要是借助next函数的定义式：，其他情况，当此集合非空时且时，当1'...''...'jk1|kax1j0][next1111jkjkppppMj设计循环借助if语句对每个j值对应的next[j]进行逐一判断，如果是第一种和第三种情况，直接将0或者1存入next数组，当遇到第二种情况时，保持i,j不变，变换k的值，判断'...''...'1111jkjkpppp是否成立，并将使“等式”成立的最大的k存入next数组。在求出所有j的next函数值后，输出数组即可。该函数C语言定义如下：voidgetnext(seqstringp,intnext[]){inti,j;next[0]=-1;//next[0]放上-1i=0;//指向字符串每个字符的指针j=-1;while(ip.length){//没有到达结尾的话if(j==-1||p.string[i]==p.string[j]){//如果是第一个字符或遇到相同的字符i++;j++;next[i]=j;}elsej=next[j];}printf(\nj的值：);for(i=0;ip.length;i++)printf(%4d,i+1);//输出j]值printf(\nnext数组：);for(i=0;ip.length;i++)printf(%4d,next[i]+1);//输出next[]值}（3）单行模式匹配函数KMP：函数参数是主串t，模式串p及next数组。从首位开始逐个比较模式穿与主串，当参与比较的两个位置字符相等时i，j自增，当字符不相等时i保持不变，j变为next[j]后继续比较。匹配成功时，列位置加入linpos数组，只带整个主串全部比较完毕。intKMP(seqstringt,seqstringp,intnext[]){inti,j;i=j=0;linpos[20]={0};for(k=0;it.length;k++){while(jp.length){4if(j==-1||t.string[i]==p.string[j]){i++;j++;}elsej=next[j];}if(j==p.length)linpos[k]=(i-p.length);j=0;}if(linpos[0]!=0)return1;if(linpos[0]==0)return-1;}（4）主函数main：连接以上各函数，实现模式串的输入和C程序文件的读取，以及结果（模式串在主串中的位置）的输出。文件的读取需要借助C语言文件打开函数fopen，在读取文件文件后，以’\n’作为行与行之间的分隔符，借助fgets等函数实现C程序文件的分行读取。分行读取完成后把每行构成的字符串转化为顺序串结构体，带入KMP函数即可计算出模式串在每行中的位置。当位置非空时，输出行数和位置坐标记录数组linepos即可。intmain(){seqstringbufstr,p;intnext[50];printf(请输入模式串:);scanf(%s,p.string);p.length=strlen(p.string);getnext(p,next);printf(\n\n模式串所在的位置为：);printf(\n行列);//开始读取程序文件charbuf[MAX_LINE];//缓冲区FILE*fp;//文件指针intlen,i=0;//行字符个数if((fp=fopen(H:\\数据结构\\KMP字符串匹配算法\\KMP算法_调试.cpp,r))==NULL){perror(failtoread);exit(1);}while(fgets(buf,MAX_LINE,fp)!=NULL){//分行读取程序文件len=strlen(buf);buf[len-1]='\0';//去掉换行符i++;strcpy(bufstr.string,buf);//把行串转化为顺序串结构体以带入KMP函数bufstr.length=len;if(KMP(bufstr,p,next)!=-1&&linpos[0]!=1028){5if(i!=27){printf(\n%25d,i);for(inta=0;a(k-1);a++)printf(%5d,linpos[a]+1);}}}}六、程序测试及检验用于检验的C程序文件地址为“H:\\数据结构\\KMP字符串匹配算法\\KMP算法_调试.cpp”，如果更换测试文件或者文件地址改变，需要在程序的相应位置处改变文件地址。1.编译并运行文件，输入要查找的模式串为“printf”，运行敞口截图如下：结果显示在原文件中的相应行和列存在模式串“printf”，其中列标只有一个数字的表明改行模式串进出现一次，有两个数字的表明改行模式串出现两次。在检验文件中查找该字符串，不多也不少且位置匹配准确，部分截图如下。加上空格后与编译软件显示的行列坐标相同，表明算法正确，程序无误。62、再次检验程序，输入模式串“i++”，运行窗口截图如下：在检验文件中查找该模式串，既没有漏也没有多，且位置匹配正确，部分摘录如下。表明算法准确，程序无误。七、算法优缺点分析优点：（1）算法匹配结果准确，实现全文多行、一行多个的精确匹配，能找到主串中所有与模式串相匹配的位置。（2）输出结果美观得体，便于读懂。缺点：（1）改变主串文件时需要在代码中改变文件地址，这使得更换主串文件较为繁琐。（2）算法和程序中仍然存在有待优化和改进的地方。八、程序代码#includestdio.h#includestdlib.h#includestring.h#defineMAX_LINE10247intk;intlinpos[20]={0};//设置全局变量typedefstructseqstring{charstring[MAX_LINE];intlength;}seqstring;voidgetnext(seqstringp,intnext[]){inti,j;next[0]=-1;//next[0]放上-1i=0;//指向字符串每个字符的指针j=-1;while(ip.length){//没有到达结尾的话if(j==-1||p.string[i]==p.string[j]){//如果是第一个字符或遇到同的字符i++;j++;next[i]=j;}elsej=next[j];}printf(\nj的值：);for(i=0;ip.length;i++)printf(%4d,i+1);//输出next[]值printf(\nnext数组：);for(i=0;ip.length;i++)printf(%4d,next[i]+1);//输出next[]值}intKMP(seqstringt,seqstringp,intnext[]){inti,j;i=j=0;linpos[20]={0};for(k=0;it.length;k++){while(jp.length){if(j==-1||t.string[i]==p.string[j]){i++;j++;}elsej=next[j];}if(j==p.length)linpos[k]=(i-p.length);j=0;}if(linpos[0]!=0)return1;if(linpos[0]==0)return-1;}8intmain(){seqstringbufstr,p;intnext[50];printf(请输入模式串:);scanf(%s,p.string);p.length=strlen(p.string);getnext(p,next);printf(\n\n模式串所在的位置为：);printf(\n行列);charbuf[MAX_LINE];//缓冲区FILE*fp;//文件指针intlen,i=0;//行字符个数if((fp=fopen(H:\\数据结构\\KMP字符串匹配算法\\KMP算法_调试.cpp,r))==NULL){perror(