C语言程序，运行时KMP算法为什么比BF算法要慢？

Question

求大佬帮忙修改一下程序，为什么运行出来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;

}

Answer 1

BM属于贪心算法，适应于实际应用。
KMP是稳定算法，不在乎特例。
一般的BM算法很容易构造m*n的特例，不过实际应用中比较少见。当然BM算法也可以改造成稳定的，构造模式比KMP需要多一些时间。