KMP之next[],nextval[]值的推导,以传统0下标开始的

[MiaoMiao]

* KMP算法是在已知模式串next[]值的基础上执行的
* next[]值仅取决于模式串本身


---------------------------------------------------------------------------
next[]的定义:
next[j]=
=0 当 j=1 时
=max{k|1<k<j且'P(1)...P(k-1)'='P(j-k+1)...P(j-1)'}当此集合非空时
=1 其它情况

---------------------------------------------------------------------------
下面以一个例子解释上面的定义
设有:
--------------------------------
j : 1 2 3 4 5 6 7 8
string: a b a a b c a c
--------------------------------
求出:next[j]=?
首先,next[1]=0
--------------------------------
j : 1 2 3 4 5 6 7 8
string : a b a a b c a c
next[j]: 0
--------------------------------
求next[j+1]=? --(j=1)
1<k<j, j=1,
so, next[2]=1
--------------------------------
j : 1 2 3 4 5 6 7 8
string : a b a a b c a c
next[j]: 0 1
--------------------------------
求next[3]=next[j+1]? --(j=2)
因:next[2]=1,又,P(1)!=P(2),又next[1]=0
所以next[3]=1
--------------------------------
j : 1 2 3 4 5 6 7 8
string : a b a a b c a c
next[j]: 0 1 1
--------------------------------
求next[4]=?
因next[3]=1,P(3)=P(1)
所以next[4]=next[3]+1=2
--------------------------------
j : 1 2 3 4 5 6 7 8
string : a b a a b c a c
next[j]: 0 1 1 2
--------------------------------
next[5]=?
next[4]=2 => P(4)!=P(2) ,
next[2]=1 => P(4) =P(1) ,
next[5]=next[2]+1=2
--------------------------------
j : 1 2 3 4 5 6 7 8
string : a b a a b c a c
next[j]: 0 1 1 2 2
--------------------------------
next[6]=?
next[5]=2 => P(5)=P(2)
next[6]=next[5]+1=3
--------------------------------
j : 1 2 3 4 5 6 7 8
string : a b a a b c a c
next[j]: 0 1 1 2 2 3
--------------------------------
next[7]=?
next[6]=3 ==> P(6)!=P(3),
next[3]=1 ==> P(6)!=P(1),
又next[1]=0
so,next[7]=1
--------------------------------
j : 1 2 3 4 5 6 7 8
string : a b a a b c a c
next[j]: 0 1 1 2 2 3 1
--------------------------------
next[8]=?
next[7]=1 ==> P(7)=P(1)
so,next[8]=next[7]+1=2
--------------------------------
j : 1 2 3 4 5 6 7 8
string : a b a a b c a c
next[j]: 0 1 1 2 2 3 1 2
--------------------------------

##################################################
##################################################
可以看出,求next[]的过程,只要确定了next[1]=0后,
剩下的就可以依次递推出来了

由此可得算法,
但相对上述有所改动.
原因是:在C种传统上数组下标是从0开始的,
因此,得:

int *
get_next( const char *const str )
{
int *next,len=strlen(str),i,j;
assert(NULL!=(next=(int *)malloc(sizeof(int)*(len))));
for(next[0]=-1,i=1,j=-1; i<len; ++i ){
for(j=i-1;j!=-1&&str[j]!=str[next[j]];j=next[j])
;
next[i]=(j!=-1&&str[j]==str[next[j]])?next[j]+1:0;
}
return next;
}
int
main(int argc, char **argv)
{
const char a[]="abcabaa";
const char
b[]="abcabaabcaabaabcabaabcabaabaabcaabaabaabaabcacabaa";
int * next1=get_next(a);
int i,j;
for(i=0;i<strlen(a);++i){
printf("%d ",next1[i]);
}
putchar(' ');
for(i=0,j=0;i<strlen(b);){
if(j==strlen(a)){
printf("%d ",i-strlen(a));
j=0;
}
j=(-1==j)?(++i,0):a[j]==b[i]?(++i,j+1):next1[j];
}
exit(0);
}

KMP算法中next[j]的求法
P为模式串
1. j=1时, next[j]=0; j=2时, next[j]=1;
2. 设k=next[j],如果P[k]==P[j], 则next[j+1]=next[j]+1;
否则, 比较P[next[k]]与P[j], 若相等,则next[j+1]=next[k]+1;
否则, 继续比较P[next[next[k]]]与P[j]........
若一直不成功, 则next[j+1]=1

改进算法中nextval函数的求法（在已知next[j]的基础上）
1. 设k=next[j],若P[j]==P[k],
则对比P[j]与P[next[k]],若相等，则继续对比P[j]与P[next[next[k]]],直到不等时，则nextval[j]=不等是
的下标。
2. 若P[j]不等于P[k], nextval[j]=k

int *
get_nextval( const char *const str,int *const next )
{
int i,j,len=strlen(str);
for(i=1; i<len; ++i){
if((j=next[i])!=0&&str[i]==str[j])
next[i]=next[j];
}
return next;
}