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

    1. T=”abcdex”（如表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。

    1. T=”abcabx”（如表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（由‘p1…pk-1’=‘pj-k＋1…pj-1’，得到p1=p4）因此next[5]=2； 6）当j=6时，j由1到j-1的串是“abcab”，由于前缀字符“ab”与后缀“ab”相等，所以next[6]=3。

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

    1. T=”ababaaaba”（如表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。

    1. T=”aaaaaaaab”（如表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。