void getNext(const char* pattern,int next[])
{
next[0]= -1;
int k=-1,j=0;
while(pattern[j] != '/0')
{
if(k!= -1 && pattern[k]!= pattern[j] )
k=next[k];
++j;++k;
if(pattern[k]== pattern[j])
next[j]=next[k];
else
next[j]=k;
}
定义:
(1)next[0]=
-1 意义:任何串的第一个字符的模式值规定为-1。
-1 意义:任何串的第一个字符的模式值规定为-1。
(2)next[j]=
-1 意义:模式串T中下标为j的字符,如果与首字符
-1 意义:模式串T中下标为j的字符,如果与首字符
相同,且j的前面的1—k个字符与开头的1—k
个字符不等(或者相等但T[k]==T[j])(1≤k<j)。
如:T=”abCabCad” 则 next[6]=-1,因T[3]=T[6]
(3)next[j]=k 意义:模式串T中下标为j的字符,如果j的前面k个
字符与开头的k个字符相等,且T[j]
!= T[k] (1≤k<j)。
!= T[k] (1≤k<j)。
即T[0]T[1]T[2]。。。T[k-1]==
T[j-k]T[j-k+1]T[j-k+2]…T[j-1]
且T[j] != T[k].(1≤k<j);
(4) next[j]=0 意义:除(1)(2)(3)的其他情况。