kmp算法_实验报告

《kmp算法_实验报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

3、x{k11

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

5、配函数即可实现全文的模式匹配。四、相关数据结构及基本操作4.1顺序串结构体的定义本算法需耍用到申结构，顺序申适用一组连续的存储单元存储申值得字符序列，在串的定长顺序结构中，按照预定义的大小为每个定义的串变量分配一个固定长度的存储区，串的实际长度可以在这预定义长度内随意变动，超过预定义长度则会被舍去。结构体成员毡括字符数组和数组长度，顺序串的结构体C语言定义如下：typedefstructseqstring{charstring[MAX_LINE];intIength;}seqstring4.2串的基本操作串的基本操作函数含在标准函数库＜8川1^上〉中，包拈求串长Strl

6、en、串赋值StrAssign、串连接Concat、串比较StrCompare、求字串Substring等，己经能够满足本算法需求，不需要重新定义新的操作函数。五、算法设计为了实现算法功能，并满足结果动态演示的需求，该算法的基本部分应该包括以下几个模块：(1)串的结构体定义(2)求next数组的函数getnext主要是借助next函数的定义式：0,当j=财next[y]=1，其他情况设计循环借助if语句对每个y值对应的/w^/77进行逐一判断，如果是第一种和第三种情况，直接将0或者1存入next数组，当

7、遇到第二种情况时，保持i，j不变，变换k的值，判断是否成立，并将使“等式”成立的最大的k存入next数组。在求出所有J的next函数值后，输出数组即可。该函数C语言定义如下：voidgetnext(seqstringp,intnext口){inti，j;next[0]=-1;//next[0]放上Hi=0;//指向字符串每个字符的指针J=-1；while(i〈p.length){//没有到达结尾的话if(j==-1IIp.string[i]==p.string[j]){//如果是第一个字符或遇到相同的字符i++;j++;next[i]=j