KMP中起到加速的是借助预先通过处理模式串得到的next数组，它存放了最长可匹配前缀子串的结尾字符下标。
但next数组求解也是最令人觉得疑惑的，通过自己的理解梳理一下以供日后回忆。
1.next数组求解的代码
private static int[] getNexts(char[] p, int pLen) {
int[] next = new int[pLen];
next[0] = -1;//没得回溯
int k = -1;//最长可匹配前缀初始也是-1
for (int i = 1; i < pLen; i++) {
while (k!=-1 && p[k+1]!=p[i]){
k = next[k];
}
if (p[k + 1] == p[i]) {
++k;
}
next[i] = k;
}
return next;
}
记住一点：上面的k是当前位置最长可匹配前缀子串的结尾字符下标。
2.next数组求解分析
1.PNG
假设已求出next[i-1]=k，x是k下一个数，y是 i-1下一个数，p[0~k] = p[r ~ i-1]。
这里存在两种情况:
(1) x== y
也就是p[k+1]==p[i]。显然，在这种情况下p[0~k+1] = p[r~i]，所以此时next[i]=k+1。
(2) x != y
也就是p[k+1] != p[i]。那这种情况怎么办？
这时我们没办法找到更长的可匹配前后缀了。但我们还可以找次长可匹配前后缀。因为已知 p[0~k] = p[r~i-1] ，那么可以得到次长可匹配前后缀 p[0~t] = p [ p~i-1]。
2.PNG
又能推出p[0~t] = p[b~k]， p[r~n] = p[p~i-1] 。
3.PNG
现在唯一能确定的是p[0~t] = p [ p~i-1] 在最长可匹配前后缀范围内，属于可匹配前后缀，但怎样能确定p[0~t] = p [ p~i-1]就是次长可匹配前后缀呢？
还记得next数组存放的是啥吗——当前位置最长可匹配前缀子串的结尾字符下标。
目前能找到的和最长后缀匹配的最长前缀范围是0~k，next[k]求得的就是k位置所在的最长可匹配前缀子串的结尾字符下标，也就是说次长前缀就是next[k]。
假设 t 所在位置就是next[k]，那么p[0~t] = p [ p~i-1]就是次长可匹配前后缀。
找这个干啥呢？既然 p[0~k+1] 和 p[ r~i] 无法匹配，那我就从 t+1开始和 i 位置继续往下看能不能匹配。
