关于KMP算法中next数组的构造

KMP算法中根据模式串来构造next数组是整个算法中最核心的步骤。KMP算法中主串和模式串（Pattern）的匹配过程是比较清晰易懂的，而next数组有多种求解方法，大多比较抽象复杂（简单的笨方法也有，那就是按照数据结构课本上的步骤，先求出模式串所有的前缀子串，然后一一求得这些前缀子串的最长相等前后缀长度）。
这里给出利用归纳法的思想获得next数组的方法，为方便转化为代码，next数组的下标j从0开始。P表示模式串。

1.Next[0]必定为-1，当模式串的第一个字符就不匹配时，需要将模式串向后移动一位，并从模式串的第一位重新开始比较。（实际操作时这种情况按照成功匹配处理）。
2.当next[0]~next[j]（闭区间）全部已知时，则接下来的目标是求得next[j + 1]。
2.1 next[j]的值的意义为：当模式串P[j]元素发生了不匹配时，j需要移动到的位置。
2.2 当j移动完成后，此时P[0,j)有一后缀与P[0, next[j])相同。
2.3 若此时P[j]与P[next[j]]相同，那么意味着上一步的相同后缀长度可以向后增加1位。即P[0,j + 1)有一后缀与P[0, next[j] + 1)相同。
2.4 由next数组的意义反推可知：此时next[j + 1] = next[j] + 1。
2.5 若此时P[j]与P[next[j]]不相同，那么不断重复j = next[j]，直到找到P[j]与P[n[j]]相同的情况。即在满足P[0,j)有一后缀与P[0, next[j])相同的条件下，不断将模式串后移，直到找到P[j]与P[next[j]]相同的情况。（根据next数组的意义，可以知道next[j]一定小于j，所以next[next[j]]也一定是已知的。）
2.6 此时满足2.3与2.4的条件，那么next[j + 1] = next[j] + 1。
3.经过第2步一系列处理之后我们得到了next[j + 1],根据归纳法，我们可以不断重复整个过程直到得到全部的next数组为止。