资源描述：
《简单匹配算法和kmp算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、实现字符串匹配的简单匹配算法和KMP算法，并且使用相同的比较字符串重复比较至少5000次，计算两者的时间差别。实验要求：完成实验内容要求，编写程序实现。提交报告，报告分三部分内容：1）自己是怎么做的？遇到什么问题，怎样解决的？2）用了哪些数据，得到什么结果？程序结果是不是跟你想的一样？为什么不一样？3）还有哪些值得改进或者不懂的？一、实验方案源程序的头文件定义为：#include#include#include#include又作出以下宏定义方便编程：#defineOVERFLOW-2#define
2、OK1#defineMAXSTRLEN255源程序中的各个函数原型如下所示：typedefcharSString[MAXSTRLEN+1];intIndex(SStringS,SStringT,intpos){//按照普通匹配查找方式查找模式串inti=pos;intj=1,k=0;while(i<=(int)S[0]&&j<=(int)T[0]){if(S[i]==T[j]){++i;++j;}else{i=i-j+2;j=1;}k++;}printf("普通匹配查找的时间复杂度为%d。",k);if(j>T[0])returni-T[0];elsereturn0;}/
3、/Indexvoidget_next(SStringT,intnext[]){//求KMP算法中的next函数值，并存入数组next[]inti=1;next[1]=0;intj=0;while(i<(int)T[0]){if(j==0
4、
5、T[i]==T[j]){++i;++j;if(T[i]!=T[j])next[i]=j;elsenext[i]=next[j];}elsej=next[j];}}//nextintIndex_KMP(SStringS,SStringT,intpos){//KMP算法的实现过程intnext[MAXSTRLEN];inti=pos;intj=
6、1,k=0;while(i<=(int)S[0]&&j<=(int)T[0]){if(j==0
7、
8、S[i]==T[j]){++i;++j;}else{get_next(T,next);j=next[j];}k++;}printf("KMP匹配查找的时间复杂度为%d。",k);if(j>(int)T[0])returni-T[0];elsereturn0;}//Index_KMP源程序中主函数如下：voidmain(){SStringT,S;intp,i,j,k1,k2;p=1;i=1;j=1;printf("请输入字符串匹配主串：");gets(&S[1]);prin
9、tf("请输入字符串匹配模式串：");gets(&T[1]);for(i=1;S[i]!=NULL;i++){S[0]=(int)(i);}printf("字符串匹配中主串：");puts(&S[1]);for(j=1;T[j]!=NULL;j++){T[0]=(int)(j);}printf("字符串匹配中模式串：");puts(&T[1]);printf("——————————普通算法————————————");k1=Index(S,T,p);printf("普通匹配算法得模式串位置：%d",k1);printf("——————————KMP
10、算法————————————");k2=Index_KMP(S,T,p);printf("KMP算法得模式串位置：%d",k2);}一、实验结果和数据处理（1）程序运行时，输入主串为S=’qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqws‘；模式串为T=’qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq
11、qqqqqqqqqqqqqqqqqqqqqws’；运行界面如下：小结：得到普通匹配算法的时间复杂度为3793，而KMP算法的时间复杂度为174，显然在匹配算法中，KMP算法优于普通算法，节省了时间以及资源。（2）当输入主串为S=’ASTRINGSEARCHINGEXAMPLECONSISTINGOFSIMPLETEXT’；模式串为T=’STING’运行结果如下：小结：当主串重复出现的字符不多时，KMP算法的优势无法明显体现出来。
