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

实现字符串匹配的简单匹配算法和KMP算法，并且使用相同的比较字符串重复比较至少5000次，计算两者的时间差别。

实验要求：
完成实验内容要求，编写程序实现。提交报告，报告分三部分内容：
自己是怎么做的？遇到什么问题，怎样解决的？
用了哪些数据，得到什么结果？程序结果是不是跟你想的一样？为什么不一样？
还有哪些值得改进或者不懂的？

实验方案
源程序的头文件定义为：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>

又作出以下宏定义方便编程：
#defineOVERFLOW-2
#defineOK1
#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。\n",k);
if(j>T[0])
returni-T[0];
elsereturn0;
}//Index

voidget_next(SStringT,intnext[])
{//求KMP算法中的next函数值，并存入数组next[]
inti=1;
next[1]=0;
intj=0;
while(i<(int)T[0])
{
if(j==0||T[i]==T[j])
{
++i;
++j;
if(T[i]!=T[j])next[i]=j;
elsenext[i]=next[j];
}
elsej=next[j];
}
}//next

intIndex_KMP(SStringS,SStringT,intpos)
{//KMP算法的实现过程
intnext[MAXSTRLEN];
inti=pos;
intj=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])
returni-T[0];
elsereturn0;
}//Index_KMP

源程序中主函数如下：
voidmain()
{
SStringT,S;
intp,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)(i);
}
printf("字符串匹配中主串：\n");
puts(&S[1]);
for(j=1;T[j]!=NULL;j++)
{
T[0]=(int)(j);
}
printf("\n字符串匹配中模式串：\n");
puts(&T[1]);
printf("——————————普通算法————————————\n");
k1=Index(S,T,p);
printf("普通匹配算法得模式串位置：%d\n\n",k1);
printf("——————————KMP算法————————————\n");
k2=Index_KMP(S,T,p);
printf("KMP算法得模式串位置：%d\n",k2);
}

实验结果和数据处理
（1）程序运行时，输入主串为
S=’qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqws‘；
模式串为
T=’qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq