利维坦mini:数据结构

next[1]=0 (4.5)
　　设next[j]=k，即有：
　　”t1 t2 … tk-1 ” =”tj-k+1 tj-k+2 … tj-1 ” (4.6)
　　next[j+1]=? 可能有两种情况：
　　第一种情况：若tk ＝tj 则表明在模式串中
　　”t1 t2 … tk ” =”tj-k+1 tj-k+2 … tj ” (4.7)
　　这就是说next[j+1]=k+1，即
　　next[j＋1]=next[j]+1 (4.8)
　　第二种情况：若tk ≠tj 则表明在模式串中
　　”t1 t2 … tk ”≠”tj-k+1 tj-k+2 … tj ” (4.9)
　　此时可把求next函数值的问题看成是一个模式匹配问题，整个模式串既是主串又是模式，而当前在匹配的过程中，已有(4.6)式成立，则当tk ≠tj 时应将模式向右滑动，使得第next[k]个字符和“主串”中的第j个字符相比较。若next[k]=k′，且t k′＝tj，则说明在主串中第j+1个字符之前存在一个最大长度为k′的子串，使得
　　”t1 t2 … t k′ ”=”tj-k′+1 tj- k′+2 … tj ” (4.10)
　　因此： next[j+1]=next[k]+1 (4.11)
　　同理若t k′ ≠tj，则将模式继续向右滑动至使第next[k′]个字符和tj 对齐，依此类推，直至tj 和模式中的某个字符匹配成功或者不存在任何 k′(1< k′<k <…<j)满足(4.10)，此时若t1≠tj+1 ， 则有：next[j+1]=1 (4.12)
　　否则若t1=tj+1 ，则有：next[j+1]=0 (4.13)
　　综上所述，求next函数值过程的算法如下：
　　void GetNext(char *t,int next[ ])
　　/*求模式t的next值并寸入next数组中*/
　　｛ int i=1,j=0;
　　next[1]=0;
　　while (i<t[0])
　　{ while (j>0&&t!=t[j]) j=next[j];
　　i++; j++;
　　if (t==t[j]) next=next[j];
　　else next=j;
　　}
　　}