#include<time.h>
#include <iostream.h>
#include <string.h>
int Index_BF ( char S [ ], char T [ ], int pos )
{
int i = pos, j = 0;
while ( S[i+j] != '\0'&& T[j] != '\0')
if ( S[i+j] == T[j] )
j ++;
else
{
i ++; j = 0; }
if ( T[j] == '\0')
return i;
else
return -1;
}
void get_nextval(const char *T, int next[])
{
int j = 0, k = -1;
next[0] = -1;
while ( T[j/*+1*/] != '\0' )
{
if (k == -1 || T[j] == T[k])
{
++j; ++k;
if (T[j]!=T[k])
next[j] = k;
else
next[j] = next[k];
}// if
else
k = next[k];
}
}
int KMP(const char *Text,const char* Pattern) //const 表示函数内部不会改变这个参数的值。
{
if( !Text||!Pattern|| Pattern[0]=='\0' || Text[0]=='\0' )//
return -1;//空指针或空串，返回-1。
int len=0;
const char * c=Pattern;
while(*c++!='\0')//移动指针比移动下标快。
{
++len;//字符串长度。
}
int *next=new int[len+1];
get_nextval(Pattern,next);//求Pattern的next函数值
int index=0,i=0,j=0;
while(Text[i]!='\0' && Pattern[j]!='\0' )
{
if(Text[i]== Pattern[j])
{
++i;// 继续比较后继字符
++j;
}
else
{
index += j-next[j];
if(next[j]!=-1)
j=next[j];// 模式串向右移动
else
{
j=0;
++i;
}
}
}//while
delete []next;
if(Pattern[j]=='\0')
return index;// 匹配成功
else
return -1;
}
int main()//abCabCad
{
int i;
char* text= "bababCabCadca";
char*pattern="adCadCad";
cout<<("主串为: ")<<endl;
cout<<("bababCabCadca")<<endl;
cout<<("子串为: ")<<endl;
cout<<("adCadCad")<<endl;
clock_t start, finish;
double duration;
//普通匹配算法
cout<<( "Time to do Index loops is ") ;
start = clock();
for(int k=0;k<5000000;k++)
{
i=Index_BF(text,pattern,1);
}
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
cout<<( "%f seconds\n", duration )<<endl;
//KMP匹配算法
cout<<( "Time to do KMP loops is ")<<endl;
start = clock();
for(int j=0;j<5000000;j++)
{
i=KMP(text,pattern);
}
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
cout<<( "%f seconds\n", duration )<<endl;
return 0;
}
要求是实现字符串匹配的简单匹配算法和KMP算法，并且使用相同的比较字符串重复比较至少5000次，计算两者的时间差别。请使用C语言。