求大佬帮忙修改一下程序，为什么运行出来KMP反而比BF要慢呢？
#include
#include
#include
#include
clock_t start,stop,start1,stop1;
double duration,duration1;
using namespace std;
typedef struct
{
string str;
int length;
}Str;
int getlength(string ch)
{
int i=0,length=0;
while(ch[i]!='\0'){
length++;
i++;
}
return length;
}
void getNext(Str ch,int *next)
{
int j=0,k=-1;
next[0]=-1;
while(j<ch.length){
if(k==-1||ch.str[j]==ch.str[k]){
if(ch.str[++j]==ch.str[++k]){
next[j]=next[k];
}
else{
next[j]=k;
}
}
else{
k=next[k];
}
}
}
int KMP(Str S,Str T,int pos,int *next){
int i,j;
i=pos-1;
j=0;
while(i
if(S.str[i]==T.str[j]||j==-1){
i++;
j++;
}
else{
j=next[j];
}
}
if(j==T.length){
return i-j+1;
}
else
return -1;
}
int BF(Str S,Str T,int pos){
int i,j;
i=pos-1;
j=0;
while(i
if(S.str[i]==T.str[j]){
i++;
j++;
}
else{
i=i-j+2;
j=0;
}
}
if(j==T.length)
return i-j+1;
else
return -1;
}
int main(){
Str S,T;
int pos,p1,p2,N,n,k;
char s[100000];
char t[10000];
cout
cout
cin>>N;
srand(time(0));
for(k=0;k
s[k]=rand()%('z'-'a'+1)+'a';
S.str=s;
cout
cout
cout
cin>>n;
for(k=0;k
t[k]=rand()%('z'-'a'+1)+'a';
T.str=t;
cout
cout
cin>>pos;
S.length=N;
T.length=n;
int i,j;
cout<<"请输入重复次数："<<endl;
cin>>i;
j=i;
int *next=new int[T.length];
start=clock();
while(i){
getNext(T,next);
p1=KMP(S,T,pos,next);
i--;
}
stop=clock();
duration=((double)(stop-start))/CLK_TCK;
printf("KMP算法的时间%f",duration);
cout<<"使用KMP算法："<<endl;
if(p1==-1)
cout<<"主串中没有匹配的子串"<<endl;
else
cout<<"从第"<<pos<<"个字符开始找起,第一次出现子串的位置为"<<p1<<endl;
start1=clock();
while(j){
p2=BF(S,T, pos);
j--;
}
stop1=clock();
duration1=((double)(stop1-start1))/CLK_TCK;
printf("BF算法的时间%f",duration1);
cout<<"使用BF算法："<<endl;
if(p2==-1)
cout<<"主串中没有匹配的子串"<<endl;
else
cout<<"从第"<<pos<<"个字符开始找起,第一次出现子串的位置为"<<p2<<endl;
delete []next;
return 0;
}
