#include<cstdio>
#include<cstring>
typedef char* String;
void get_next(String T,int *next){
int i=0,j=1;//i表示前缀,j表示后缀
int T_len=strlen(T)-1;
next[1]=0;
while(j<T[0]){
if(0==i || T[i]==T[j]){
++i;
++j;
next[j]=i;
}
else{
i=next[i];
}
}
}
int Index_KMP(String S,String T,int pos){
int i=pos;
int S_len=strlen(S)-1;
int T_len=strlen(T)-1;
int j=1;
int next[255];
get_next(T,next);
while(i<=S_len && j<=T_len){
if(0==j || S[i]==T[j]){
++i;
++j;
}
else {
j=next[j];
}
}
if(j>T_len)return i-T_len;
else return 0;
}
int main()
{
String S=" abcdefgh";
String T=" abcdx";
printf("%d\n",Index_KMP(S,T,1));
return 0;
}
个人学习心得,,,晒晒代码。。。。 |