Question

具体如何推导出一个串的next数组值呢，我们来看一些例子。

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

表5-7-1

j	123456
模式串T	abcdex
next[j]	011111

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

2）当j=2时，j由1到j-1就只有字符“a”，属于其他情况next[2]=1；

3）当j=3时，j由1到j-1串是“ab”，显然“a”与“b”不相等，属其他情况，next[3]=1；

4）以后同理，所以最终此T串的next[j]为011111。

2．T="abcabx"（如表5-7-2所示）

表5-7-2

j	123456
模式串T	abcabx
next[j]	011123

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

2）当j=2时，同上例说明，next[2]=1；

3）当j=3时，同上，next[3]=1；

4）当j=4时，同上，next[4]=1；

5）当j=5时，此时j由1到j-1的串是“abca”，前缀字符“a”与后缀字符“a”相等（前缀用下划线表示，后缀用斜体表示），因此可推算出k值为2（由‘p₁...p_k-1’=‘p_j-k＋1...p_j-1’，得到p₁=p₄）因此next[5]=2；

6）当j=6时，j由1到j-1的串是“abcab”，由于前缀字符“ab”与后缀“ab”相等，所以next[6]=3。

我们可以根据经验得到如果前后缀一个字符相等，k值是2，两个字符k值是3，n个相等k值就是n+1。

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

表5-7-3

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

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

2）当j=2时，同上next[2]=1；

3）当j=3时，同上next[3]=1；

4）当j=4时，j由1到j-1的串是“aba”，前缀字符“a”与后缀字符“a”相等，next[4]=2；

5）当j=5时，j由1到j-1的串是“abab”，由于前缀字符“ab”与后缀“ab”相等，所以next[5]=3；

6）当j=6时，j由1到j-1的串是“ababa”，由于前缀字符“aba”与后缀“aba”相等，所以next[6]=4；

7）当j=7时，j由1到j-1的串是“ababaa”，由于前缀字符“ab”与后缀“aa”并不相等，只有“a”相等，所以next[7]=2；

8）当j=8时，j由1到j-1的串是“ababaaa”，只有“a”相等，所以next[8]=2；

9）当j=9时，j由1到j-1的串是“ababaaab”，由于前缀字符“ab”与后缀“ab”相等，所以next[9]=3。

4．T="aaaaaaaab"（如表5-7-4所示）

表5-7-4

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

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

2）当j=2时，同上next[2]=1；

3）当j=3时，j由1到j-1的串是“aa”，前缀字符“a”与后缀字符“a”相等，next[3]=2；

4）当j=4时，j由1到j-1的串是“aaa”，由于前缀字符“aa”与后缀“aa”相等，所以next[4]=3；

5）……

6）当j=9时，j由1到j-1的串是“aaaaaaaa”，由于前缀字符“aaaaaaa”与后缀“aaaaaaa”相等，所以next[9]=8。