Question

改良后，我们之前的例子nextval值就与next值不完全相同了。比如：

1．T="ababaaaba"（如表5-7-5所示）

表5-7-5

j	123456789
模式串T	ababaaaba
next[j]	011234223
nextval[j]	010104210

先算出next数组的值分别为011234223，然后再分别判断。

1）当j=1时，nextval[1]=0；

2）当j=2时，因第二位字符“b”的next值是1，而第一位就是“a”，它们不相等，所以nextval[2]=next[2]=1，维持原值。

3）当j=3时，因为第三位字符“a”的next值为1，所以与第一位的“a”比较得知它们相等，所以nextval[3]=nextval[1]=0；如图5-7-7所示。

图5-7-7

4）当j=4时，第四位的字符“b”next值为2，所以与第二位的“b”相比较得到结果是相等，因此nextval[4]=nextval[2]=1；如图5-7-8所示。

图5-7-8

5）当j=5时，next值为3，第五个字符“a”与第三个字符“a”相等，因此nextval[5]=nextval[3]=0；

6）当j=6时，next值为4，第六个字符“a”与第四个字符“b”不相等，因此nextval[6]=4；

7）当j=7时，next值为2，第七个字符“a”与第二个字符“b”不相等，因此nextval[7]=2；

8）当j=8时，next值为2，第八个字符“b”与第二个字符“b”相等，因此nextval[8]=nextval[2]=1；

9）当j=9时，next值为3，第九个字符“a”与第三个字符“a”相等，因此nextval[9]=nextval[3]=0。

2．T="aaaaaaaab"（如表5-7-6）

表5-7-6

j	123456789
模式串T	aaaaaaaab
next[j]	012345678
nextval[j]	000000008

先算出next数组的值分别为012345678，然后再分别判断。

1）当j=1时，nextval[1]=0；

2）当j=2时，next值为1，第二个字符与第一个字符相等，所以nextval[2]=nextval[1]=0；

3）同样的道理，其后都为0……；

4）当j=9时，next值为8，第九个字符“b”与第八个字符“a”不相等，所以nextval[9]=8。

总结改进过的KMP算法，它是在计算出next值的同时，如果a位字符与它next值指向的b位字符相等，则该a位的nextval就指向b位的nextval值，如果不等，则该a位的nextval值就是它自己a位的next的值。