假设有一个模式P[] = {ababc}，在一个文章中寻找模式P(假设文本不动，让P往后移动)，如果P[0]和文章的字母不相等， 则next[0] = 1;(next[i]是当P[i]是第一个不匹配的字母时，P应该向后挪动几个单位）。生成next数组的方法就是寻找最大相等的前缀和后缀，即若P[j]不匹配，从0...j-1中寻找最大的k，P[0...k] = P[j - 1-k...j-1]; k != j-1;如果k为j-1，next[j] = j; 所以next[0] = 1; next[1] = 1; next[2] = 2; next[3] = 2, next[4] = 2;
这里简单说明为什么一定要取最大的k，比如说有模式字符串a b c a b c a d c,假设在P[7]'d'的位置是错误的，发现P[0] = P[6] = "a"(k = 0), 同时发现P[0..3] = P[3...6]="abca"(k = 3)，
a b c a b c a d c
0 1 2 3 4 5 6 7 8
next[7]应该选择3，而不是6。例如文本的数据是：
a b c a b c a b c a d c
0 1 2 3 4 5 6 7 8 9 10 11
如果是选择6，情景如下：
a b c a b c a b c a d c
0 1 2 3 4 5 6 7 8 9 10 11
P a b c a b c a d c
发现最终该文本没有匹配模式的串。实际是有的，就是Text[3...11]
如果选择3，情景如下：
a b c a b c a b c a d c
0 1 2 3 4 5 6 7 8 9 10 11
P a b c a b c a d c
完全匹配。就是如果存在较大的k，而选择较小的k，容易忽略一些整整匹配的模式串。
以上过程计算了next数组，它其实不是最优的next，重新认识最上面的模式P= {ababc}：
next[0] = 1; next[1] = 1; next[2] = 2; next[3] = 2, next[4] = 2;
next[0] = 1, next[1] = 1都没有问题，问题是next[2] = 2,
Text ？
T1 a b a b c
T2 a b a b c(相对于T1时刻移动了2个单位)
这肯定不是匹配的解，因为next[k]的含义是第k个字符不匹配移动的单位数，已经知道T1时刻P[2]对应的文本？不是'a', 所以T2时刻的P是不会匹配的，所以还可以接着向后移动。该优化的突破点在于P[j] 和P[j - next[j]]是否相等。若不相等，正常；若相等，就要进一步优化。伪代码如下：
while (P[j] = P[j - next[j]])
next[j] = next[j] + next[j - next[j]];
end
注意，上面递归用到了next[j]，一定要从小到大计算next[j]（j 从0到length(P)），只有这样，求解的方案才是最优的，不然，可能不是最优的。