#include
#include
#include
using namespace std;
#define MAXSTRKEN 20
int k_BF=0,k_KMP=0,k_next=0;
typedef struct
{
char ch[MAXSTRKEN];
int length;
}SString;
void get_next(SString T, int next[])
{
int j = 0,i = -1;
next[0] = -1;
while (j<T.length)
{
if ((i==-1) || T.ch == T.ch[j])
{
++i;
++j;
next[j]=i;
}
else
i = next;
k_next++;
}
}
int Index_BF(SString S, SString T)
{
int i=0,j=0;
while (i <= S.length-1 && j <= T.length-1)
{
if (S.ch == T.ch[j])
{
++i;
++j;
}
else
{
i = i-j+1;
j = 0;
}
k_BF++;
}
if (j =T.length)
returni-T.length;
else
return -1;
} // Index` (朴素算法)
int Index_KMP(SString S, SString T)
{
int i = 0,j = 0;
while (i <= S.length -1 && j <= T.length -1)
{
if (j == -1 || S.ch == T.ch[j])
{
++i;
++j;
}
else
j = next[j];
}
k_KMP++;
if (j =T.length)
returni-T.length;
else
return 0;
} // Index_KMP
int main()
{
int i,j;
SString S,T;
S.length=0;
T.length=0;
cout<<"请输入主串：S=";
while(S.ch=getchar()!='\n')
{
i++;
S.length++;
}
cout<<"请输入模式串：T=";
while(T.ch=getchar()!='\n')
{
i++;
T.length++;
}
Index_BF(S,T);
Index_KMP(S,T);
cout<<"主串长："<<S.length<<endl;
cout<<"模式串长："<<T.length<<endl;
cout<<"BF算法比较次数为："<<k_BF<<endl;
cout<<"KMP算法比较次数为："<<k_KMP+k_next<<endl;
cout<<"next比较次数为："<<k_next<<endl;
}
|
