编制kmp字符串匹配实验报告.doc

实验报告题目：编制字符串匹配的KMP算法班级：OOO 姓名：XXX 学号：ASDFGHJK 完成日期：20XX.XX.XX1、 需求分析1. 字符串匹配试求子串位置的定位函数，普通的字符串匹配函数时间复杂度较大达到了O（m*n），而KMP算法则可以将时间复杂度简化到O（m+n）。2. 本演示程序中，字符串的元素为除换行、退格等字符外的其他字符，字符串长度=MAXSIZE，字符串的输入的形式为string0储存长度，从string1开始存储字符，并以0做结束标志，字符串中字符顺序不限，且允许出现重复字符，不能出现非法字符。输入两个字符串后，输入一个整形数pos，pos=0数据关系：R1=|ai-1,aiD,i=1,2,.,n基本操作：GetString(SString &S)初始条件：存在串的指针。操作结果：生成一个由键盘键入的字符串S。strlen(SString S)初始条件：串S存在。操作结果：返回S的元素个数，称为串的长度。Index(SString S,SString T,int pos)初始条件：串S和T存在，T是非空串，1=posGetString()-strlenth() -index_KMP-get_next()3、 调试分析1. 在GetString()中开始用了gets(S)，S0没有用来记录字符串的长度，导致在后续的程序中运算出错。2. next函数在某些情况下存在缺陷。例如模式aaaaa在和主串aaabaaaab匹配时，当i=4、j=4，时不匹配，需要进行多余的三次比较，实际上，因为模式中第1、2、3、个字符和第4个字符都相等，因此不再需要和主串中第四个字符进行比较，而可以将模式一气向右滑动4个字符的位置直接进行i=5、j=1时的字符比较。这就是说，若按上述定义得到nextj=k，而模式中pj=pk，则当主串中字符si和pj不比较不等时，不需要在和pk进行比较，而直接和pnextk进行比较，即此时的nextj应该和nextk相同。由此得到修正算法：void get_nextval(SString T,int nextval)四、测试结果1.S=abababab T=aba pos=1 :1;2.S=abababab T=aba pos=6 :0;五、附录源程序文件清单：#define MAXSTRLEN 255#include#include#includeint nextMAXSTRLEN+1,nextvalMAXSTRLEN+1;typedef char SStringMAXSTRLEN+1;int Index_KMP(SString S,SString T,int pos)int i,j=1;i=pos;while(i=S0&jT0)return i-T0;else return 0;void get_next(SString T,int next)int i=1,j;next1=0;j=0;while(iT0)if(j=0|Ti=Tj)+i;+j;nexti=j;else j=nextj;void get_nextval(SString T,int nextval)int i=1,j=0;nextval1=0;while(iT0)if(j=0|Ti=Tj)i+;j+;if(Ti!=Tj)nextvali=j;else nextvali=nextvalj;else j=nextvalj;void GetString(SString &S)gets(S+1);S0=strlen(S+1);int main()SString S,T;int pos;GetString(S);Get