求 KMP改进算法 BM 改进算法
QQ 63815710
KMP算法:
int index(String S,String T,int pos)
{
int i=pos;int j=1;
while(i<=S.length&&j<=T.length)
{
if(S[i]==T[j]){i++;j++}
else{i=i-j+2;j=1;}
}
if(j>=T.length) return i-T.length
}
改进的KMP算法
int index_KMP(String S,String T,int pos)
{
int i=pos;int j=1;
while(i<=S.length&&j<=T.length)
{
if(S[i]==T[j]){i++;j++}
else j=next[j];
}
if(j>=T.length) return i-T.length
}
void get_next(String T,int next[])
{
int i=1;next[1]=0;int j=0;
while(i<T.length)
{
if(j==0||T[i]==T[j]){i++;j++;next[i]=j;}
else j=next[j];
}
}