相关：next数组求法
对应next数组，还有nextval数组，下面介绍下如何根据next数组进一步求解nextval数组。
求解的方法为：如果str[i]与str[next[i]-1]相等，则next[i]=next[next[i]-1]。
KMP序号: 1 2 3 4 5 6 7 8 9 10 11 12
string： a b a b a a a b a b a a
next数组：0 1 1 2 3 4 2 2 3 4 5 6
数组idx： 0 1 2 3 4 5 6 7 8 9 10 11
我们依然使用上一篇文章的例子来说明，其中next数组已经在上篇文章中求得。
第二位i=1：str[i]=str[1]=’b’,str[next[i]-1]=str[0]=’a’，不相等，所以next[1]=1不变；
第三位i=2：str[i]=str[2]=’a’,str[next[i]-1]=str[0]=’a’，相等，所以next[2]=next[next[i]-1]=next[0]=0；
第四位i=3：str[i]=str[3]=’b’,str[next[i]-1]=str[1]=’b’，相等，所以next[3]=next[next[i]-1]=next[1]=1；
第五位i=4：str[i]=str[4]=’a’,str[next[4]-1]=str[2]=’a’，相等，所以next[4]=next[next[i]-1]=next[2]=0；
第六位i=5：str[i]=str[5]=’a’,str[next[5]-1]=str[3]=’b’，不相等，所以next[5]=4不变；
第七位i=6：str[i]=str[6]=’a’,str[next[6]-1]=str[1]=’b’，不相等，所以next[6]=2不变；
第八位i=7：str[i]=str[7]=’b’,str[next[7]-1]=str[1]=’b’，相等，所以next[7]=next[1]=1;
第九位i=8：str[i]=str[8]=’a’,str[next[8]-1]=str[2]=’a’，相等，所以next[8]=next[2]=0;
第十位i=9：str[i]=str[9]=’b’,str[next[9]-1]=str[3]=’b’，相等，所以next[9]=next[3]=1;
十一位i=10：str[10]=a’,str[next[10]-1]=str[4]=’a’，相等，所以next[10]=next[4]=0;
十二位i=11：str[11]=’a’,str[next[11]-1]=str[5]=’a’，相等，所以next[11]=next[5]=4;
至此，nextval数组求取完毕。
KMP序号: 1 2 3 4 5 6 7 8 9 10 11 12
string： a b a b a a a b a b a a
next数组：0 1 1 2 3 4 2 2 3 4 5 6
nextval ：0 1 0 1 0 4 2 1 0 1 0 4
数组idx： 0 1 2 3 4 5 6 7 8 9 10 11