KMP实验报告

实验报告题目编制字符串匹配的算法KMP班级理科实验四班姓名木三学号******完成日期

2016.

4.17

一、需求分析

1.字符串匹配试求子串位置的定位函数，普通的字符串匹配函数时间复杂度较大达到了0m*n,而KMP算法则可以将时间复杂度简化到0m+n

2.本演示程序中，字符串的元素为除换行、退格等字符外的其他字符，字符串长度CMAXSIZE,字符串的输入的形式为string[]储存长度,从string[l]开始存储字符，并以0做结束标志，字符串中字符顺序不限，且允许出现重复字符,不能出现非法字符输入两个字符串后，输入一个整形数pos,pos=MAXSIZE,pos的值必须合法输出的结果为一个整形数，表示，从第一个字符串的pos位置开始，之后的子串能否与第二个字符串匹配，若能，输出匹配首地址的编号，若不能，输出

03.程序执行的命令包括1构造字符串1;2构造字符串2；3kmp算法；4得到next[]；

4.测试数据1stringl=abababab string2=,aba pos=l output=l；2stringl=abababab string2=,aba pos=6output；

二、概要设计KMP算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的一种模式匹配的高效算法，，可以在0m+n的时间数量级上完成串的模式匹配操作其改进在于每当一趟匹配过程中出现的字符比较不等时，不需要回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较为实现上述上述程序功能，应以串的定长顺序存储表示来存放字符串，且需要串的抽象数据类型L串的定长顺序存储表示为^define MAXSTRLEN255〃用户可在255以内定义最大串长typedef charSString[MAXSTRLEN+l]；〃0号单元存放串的长度2•串的抽象数据类型定义为ADT String{数据对象D={ai|ai£CharacterSet,i=l,2,...,n,n=0}数据关系Rl={ai-l,ai|ai-l,ai i=l,2,...,n基本操作GetString SString S初始条件存在串的指针操作结果生成一个由键盘键入的字符串Sstrlen SStringS初始条件串S存在操作结果返回S的元素个数，称为串的长度IndexSString S,SString T,int pos初始条件串S和T存在，T是非空串,l=pos=StrlengthS-pos+

1.操作结果若主串S中存在和串T值相同的子串，贼返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0}//ADT String

3.KMP算法中，用到next函数，定义void get_next SString T,int next[]

4.函数的调用关系图main-GetString-strlenth-index_KMP-get_next

三、调试分析

1.在GetStringO中开始用了getsS,S

[0]没有用来记录字符串的长度，导致在后续的程序中运算出错

2.next函数在某些情况下存在缺陷例如模式4aaaaa在和主串aaabaaaab匹配时，当i=

4、产4,时不匹配，需要进行多余的三次比较，实际上，因为模式中第

1、

2、

3、个字符和第4个字符都相等，因此不再需要和主串中第四个字符进行比较，而可以将模式一气向右滑动4个字符的位置直接进行；

5、时的字符比较这就是说，若按上述定义得到next[j]=k,而模式中pj二pk,则当主串中字符si和pj不比较不等时，不需要在和pk进行比较，而直接和pnext[k]进行比较,即此时的next比]应该和next[k]相同由此得到修正算法void get_nextval SStringT,int nextval[]

四、测试结果

1.S=abababab T二aba pos=l1；

2.S=abababab T=aba pos=60；

五、附录源程序文件清单#define MAXSTRLEN255#includestdio.h#includestdlib.h#includestring.hint next[MAXSTRLEN+1],nextval[MAXSTRLEN+1]；typedef charSString[MAXSTRLEN+1]；int Index_KMPSString S,SStringT,int pos{int i,j=l；i=pos；whilei=S

[0]j=T

[0]if j==0||S[i]==T[j]{i++；j++；}else j=next[j]；ifjT[O]return i-T

[0]；else return0；void get_nextSString T,int next[]{int i=l,j；next[l]=0；j=0;whileiT

[0]ifj==O||T[i]==T[j]{++i；++j；next[i]=j；else j=next[j]；void get_nextvalSString T,int nextval[]{int i=l,j=0；nextval[l]=0；whileiT

[0]ifj==O||T[i]==T[j]i++;j++;if T[i]!=T[j]nextval[i]=j；else nextval[i]=nextval[j]；else j=nextval[j]；void GetStringSStringSgetsS+l；S

[0]=strlen S+l；}int mainSStringS,T；int pos；GetStringS；GetStringT；get_next T,next；scanf%d”,pos；printfn%dn,Index_KMP S,T,pos；return0；。