最近再刷笔试题的时候，发现了几道题需要求取字符串的next数组。
关于这部分知识，之前是有学过，代码也是比较简洁的，如下：
public static int[] getNext(String ps) {
char[] p = ps.toCharArray();
int[] next = new int[p.length];
next[0] = -1;
int j = 0;
int k = -1;
while (j < p.length - 1) {
if (k == -1 || p[j] == p[k]) {
next[++j] = ++k;
} else {
k = next[k];
}
}
return next;
}
但是对于KMP的描述，《算法导论》等教材中是有些隐晦复杂的，各个博客上的讲解也不尽相同。针对next数组这一块，综合了几家之长，我也简单描述下自己的想法，可以与大家相互探讨。
因为在kmp算法中，文本中的指针i是无法回溯的，所以最关键的是，next[j]的值（也就是k）表示，当P[j] != T[i]时，j指针的下一步移动位置。其中P为匹配字符串，T为原文。也就是说next数组其实就是查找P中每一位前面的子串的前后缀有多少位匹配，从而决定j失配时应该回退到哪个位置。
作为笔试题来说，思想比较简单。就是考虑从P[0 ~ k-1] == p[j-k ~ j-1]中k的个数，基本就可以数出来了。借用他人的说法就是（字符串匹配是 从头开始的 和 从尾开始的字符串进行匹配是否重复 ）
而在计算next数组时主要是以下两个步骤：
1. 当P[k] == P[j]时，有next[j+1] == next[j] + 1。
2. 当P[k] != P[j]时，有k = next[k]。
结合1和2可知，next[j]==k;
也就是说，P[0 ~ k-1] == p[j-k ~ j-1]中k的位置决定了next[j]的值。
以下列字符串为例：
跑了一下，结果如下：
相信对每一行逐行分析后，会对求取前缀函数有更深的了解