KMP实验报告.docx

《KMP实验报告.docx》由会员分享，可在线阅读，更多相关《KMP实验报告.docx（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验报告题目：编制字符串匹配的KMP算法班级：理科实验四班 姓名：木三学号：* 完成日期：2016.4.17 一、需求分析1 .字符串匹配试求子串位置的定位函数，普通的字符串匹配函数时间复杂度较大 达到了 0 (m*n),而KMP算法则可以将时间复杂度简化到0 (m+n)。2 .本演示程序中，字符串的元素为除换行、退格等字符外的其他字符，字符串长 度CMAXSIZE,字符串的输入的形式为string。储存长度,从stringl开始存 储字符，并以0做结束标志，字符串中字符顺序不限，且允许出现重复字符, 不能出现非法字符。输入两个字符串后，输入一个整形数pos, pos=0数据关系：Rl= |a

2、i-l,ai i=l,2,. . ,n)基本操作：GetString (SString &S)初始条件：存在串的指针。操作结果：生成一个由键盘键入的字符串S。strlen (SString S)初始条件：串S存在。操作结果：返回S的元素个数，称为串的长度。Index(SString S,SString T,int pos)初始条件：串S和T存在，T是非空串,l=posGetString () -strlenth () -index_KMP-get_next()三、调试分析1.在GetStringO中开始用了 gets(S), S0没有用来记录字符串的长度，导致 在后续的程序中运算出错。2. n

3、ext函数在某些情况下存在缺陷。例如模式4aaaaa在和主串aaabaaaab 匹配时，当i=4、产4,时不匹配，需要进行多余的三次比较，实际上，因为模 式中第1、2、3、个字符和第4个字符都相等，因此不再需要和主串中第四个字 符进行比较，而可以将模式一气向右滑动4个字符的位置直接进行；5、时 的字符比较。这就是说，若按上述定义得到nextj=k,而模式中pj二pk,则当 主串中字符si和pj不比较不等时，不需要在和pk进行比较，而直接和pnextk 进行比较,即此时的next比应该和next k相同。由此得到修正算法：void get_nextval (SString T,int nextv

4、al)四、测试结果1. S=abababab?T二abapos=l ：1；2. S=ababababT=abapos=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=l；i=pos；while(i=S0&jTO)return i-T0；else return 0；)void get

5、_next(SString T,int next)int i=l,j；next l=0；j=0;while(iT0)(if(j=O|Ti=Tj)+i；+j；next i=j；)else j=nextj；)void get_nextval(SString T, int nextval)int i=l,j=0；nextvall=0；while(iT0)(if(j=O|Ti=Tj)(i+;j+;if (Ti!=Tj)nextvali=j；else nextvali=nextvalj；else j=nextvalj； void GetString(SString &S)(gets(S+l)；S0=strlen (S+l)；int main ()(SString S,T；int pos；GetString(S)；GetString(T)；get_next (T,next)；scanf(%d”,&pos)；printf(n%dn,Index_KMP (S,T,pos)；return 0；