简单匹配算法和KMP算法.doc

实现字符串匹配的简单匹配算法和KMP算法，并且使用相同的比较字符串重复比较至少5000次，计算两者的时间差别。实验要求：完成实验内容要求，编写程序实现。提交报告，报告分三部分内容：1） 自己是怎么做的？遇到什么问题，怎样解决的？2） 用了哪些数据，得到什么结果？程序结果是不是跟你想的一样？为什么不一样？3） 还有哪些值得改进或者不懂的？一、 实验方案源程序的头文件定义为：#include #include #include #include 又作出以下宏定义方便编程：#define OVERFLOW -2#define OK 1#define MAXSTRLEN 255源程序中的各个函数原型如下所示：typedef char SStringMAXSTRLEN+1;int Index(SString S,SString T,int pos) /按照普通匹配查找方式查找模式串int i=pos;int j=1,k=0;while(i=(int)S0 & jT0) return i-T0;else return 0;/Indexvoid get_next(SString T,int next) /求KMP算法中的next函数值，并存入数组next int i=1; next1=0; int j=0; while(i(int)T0) if(j=0 | Ti=Tj) +i; +j; if(Ti!=Tj) nexti=j; else nexti=nextj; else j=nextj; /nextint Index_KMP(SString S,SString T,int pos) /KMP算法的实现过程int nextMAXSTRLEN;int i=pos;int j=1,k=0;while(i=(int)S0 & j(int)T0)return i-T0;else return 0;/Index_KMP源程序中主函数如下：void main()SString T,S;int p,i,j,k1,k2;p=1;i=1;j=1;printf(请输入字符串匹配主串：n);gets(&S1);printf(请输入字符串匹配模式串：n);gets(&T1);for(i=1;Si!=NULL;i+)S0=(int)(i);printf(字符串匹配中主串：n);puts(&S1);for(j=1;Tj!=NULL;j+)T0=(int)(j);printf(n字符串匹配中模式串：n);puts(&T1); printf(普通算法n);k1=Index(S,T,p);printf(普通匹配算法得模式串位置：%dnn,k1);printf(KMP算法n);k2=Index_KMP(S,T,p);printf(KMP算法得模式串位置：%dn,k2);二、 实验结果和数据处理（1）程序运行时，输入主串为S=qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqws ；模式串为T=qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqws；运行界面如下：小结：得到普通匹配算法的时间复杂度为3793，而KMP算法的时间复杂度为174，显然在匹配算法中，KMP算法优于普通算法，节省了时间以及资源。（2）当输入主串为S=A STRING SEARCHING EXAMPL