KMP算法_实验报告.doc

《KMP算法_实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、西安交通大学实验报告课程数据结构实验名称基于串的模式匹配第1页共页系别__自动化实验日期/2014年11月15日专业班级自动化43班实验报告日期2014年11月22日姓名李欣阳学号报告退发(订正、重做)同组人无教师审批签字一、实验目的熟练掌握串的运用，以及线性表、栈、队列等的基本操作；理解KMP模式匹配算法的原理，能够利用该算法解决实际问题。二、实验内容与要求1.自由选择一个C程序文件作为程序的输入；2.通过键盘输入待查找的模式串，求取并显示next数组；3.判断该程序代码中是否包含该模式串，如果包含，输出左右该模式串在程序代码中文件中的位置

2、（包括行数和该行的第几个字符）；4.用KMP算法进行实现。三、问题分析3.1KMP算法综述KMP算法是一个非常优秀的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，其时间复杂度为O（m+n）。该算法相对于普通匹配算法的改进在于：每当一趟匹配过程中出现字符比较不等时，不许回溯指针i，而是利用已经得到的部分匹配的结果将模式向右滑动尽可能远的一段距离后，继续进行比较。3.2next数组的计算正确求得next数组是实现KMP算法的关键，它决定了在匹配过程中出现字符不等时，模式串应该向右滑动的距离。next数组定

3、义如下：求得next数组后，匹配按照如下方式进行：假设指针i和j分别指示主串和模式串中正待比较的字符，令i初值为pos，j的初值为1，若在匹配过程中对应位置字符相等，则i和j增1；如果出现不相等的情况，则j退到next[j]的位置继续进行比较。3.3一行多次匹配的实现由于原始的KMP算法在完成一次模式匹配后会推出算法，想要实现一行多个的模式匹配，需要设计结构存储每一行模式匹配中，模式串出现的位置。因此定义数组linepos[20]来存储模式串在每一行出现的位置。具体实现方法是：在进行模式匹配是，如果在主串中出现与模式相匹配的连续串，则把该串在

4、主串中出现的位置记录到linpos数组中，此后i不归零而是继续进行匹配，知道主串中的每个字符都与模式串比较过。这样逐行重复上述算法就可以实现每一行的多次匹配。3.4C程序文件的读入算法要求能对C程序代码文件进行模式匹配，在解决单行模式匹配问题后，需要解决的就是C程序文件的读入。在读入程序文件时有两种方式，一是整体读入文件后分行存储，另一个是分行读取，为了节省内存空间优化算法，本算法采用分行读取分行匹配的方式。文件的读取需要借助C语言文件打开函数fopen，在读取文件文件后，以’’作为行与行之间的分隔符，借助fgets等函数实现C程序文件的

5、分行读取。分行读取完成后借助单行匹配函数即可实现全文的模式匹配。四、相关数据结构及基本操作4.1顺序串结构体的定义本算法需要用到串结构，顺序串适用一组连续的存储单元存储串值得字符序列，在串的定长顺序结构中，按照预定义的大小为每个定义的串变量分配一个固定长度的存储区，串的实际长度可以在这预定义长度内随意变动，超过预定义长度则会被舍去。结构体成员包括字符数组和数组长度，顺序串的结构体C语言定义如下：typedefstructseqstring{charstring[MAX_LINE];intlength;}seqstring4.2串的基本操作串的

6、基本操作函数包含在标准函数库中，包括求串长Strlen、串赋值StrAssign、串连接Concat、串比较StrCompare、求字串SubString等，已经能够满足本算法需求，不需要重新定义新的操作函数。五、算法设计为了实现算法功能，并满足结果动态演示的需求，该算法的基本部分应该包括以下几个模块：（1）串的结构体定义（2）求next数组的函数getnext主要是借助next函数的定义式：设计循环借助if语句对每个j值对应的next[j]进行逐一判断，如果是第一种和第三种情况，直接将0或者1存入next数组，当遇到第二

7、种情况时，保持i,j不变，变换k的值，判断是否成立，并将使“等式”成立的最大的k存入next数组。在求出所有j的next函数值后，输出数组即可。该函数C语言定义如下：voidgetnext(seqstringp,intnext[]){inti,j;next[0]=-1;//next[0]放上-1i=0;//指向字符串每个字符的指针j=-1;while(i

8、

9、p.string[i]==p.string[j]){//如果是第一个字符或遇到相同的字符i++;j++;next[i]=j;}el

10、sej=next[j];}printf("j的值：");for(i=0;i