文档介绍：实现字符串匹配的简单匹配算法和 KMP 算法,并且使用相同的比较字符串重复比较至少 5000 次,计算两者的时间差别。实验要求: 完成实验内容要求,编写程序实现。提交报告,报告分三部分内容: 1) 自己是怎么做的?遇到什么问题,怎样解决的? 2) 用了哪些数据,得到什么结果?程序结果是不是跟你想的一样?为什么不一样? 3) 还有哪些值得改进或者不懂的? 一、实验方案源程序的头文件定义为: #include <> #include <> #include <> #include <> 又作出以下宏定义方便编程: #define OVERFLOW -2 #define OK 1 #define MAXSTRLEN 255 源程序中的各个函数原型如下所示: typedef char SString[MAXSTRLEN+1]; int Index(SString S,SString T,int pos) { // 按照普通匹配查找方式查找模式串 int i=pos; int j=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 。\n",k); if(j>T[0]) return i-T[0]; else return 0; }//Index void get_next(SString T,int next[]) { //求 KMP 算法中的 next 函数值, 并存入数组 next[] int i=1; next[1]=0; int j=0; while(i<(int)T[0]) { if(j==0 || T[i]==T[j]) { ++i; ++j; if(T[i]!=T[j]) next[i]=j; else next[i]=next[j]; } else j=next[j]; } }//next int Index_KMP(SString S,SString T,int pos) { //KMP 算法的实现过程 int next[MAXSTRLEN]; int i=pos; int j=1,k=0; while(i<=(int)S[0] && j<=(int)T[0]) { if(j==0 || S[i]==T[j]) { ++i; ++j; } else { get_next(T,next); j=next[j]; } k++; } printf("KMP 匹配查找的时间复杂度为%d 。\n",k); if(j>(int)T[0]) return i-T[0]; 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(&S[1]); printf(" 请输入字符串匹配模式串: \n"); gets(&T[1]); for(i=1;S[i]!=NULL;i++) { S[0]=(int