匹配字串 ABABCABAA
最长公共前后缀
0 A
0 AB
1 ABA // 前缀A，后缀A
2 ABAB // 前缀AB，后缀AB
0 ABABC
1 ABABCA // 前缀A，后缀A
2 ABABCAB // 前缀AB，后缀AB
3 ABABCABA // 前缀ABA，后缀ABA
1 ABABCABAA // 前缀A，后缀A
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 匹配字串 | A | B | A | B | C | A | B | A | A |
| next数组 | 0 | 0 | 1 | 2 | 0 | 1 | 2 | 3 | 1 |
next里面的值可以看做是公共前后缀的长度，比如"ABAB"，最后一个B对应的也就是是next[3] = 2，这个2就是表示了长度（前缀"AB"，后缀"AB"）。
但是如果想直接用next[3]访问前缀的最后的B呢？把数组的每个值减1就好了。
| 新next数组 | -1 | -1 | 0 | 1 | -1 | 0 | 1 | 2 | 0 |
void nextBuilder(char[] next, String needle) {
int j = -1; //起始为-1
next[0] = j; //赋初始值，这其实是动态规划问题
//准确说j+1才是长度，但是为了方便后来不用-1，所以就用 j 啦。
//用next数组的话是 len = next[len-1] 这样回溯也很好理解了
for (int i = 1; i < needle.length(); i++) {
//如果不相等，就到 当前前后缀长度减一的前后缀 的位置
while (j >= 0 && needle.charAt(j+1) != needle.charAt(i)) {
j = next[j]; //回溯
}
//如果相等，长度+1
if (needle.charAt(j+1)) == needle.charAt(i)) {
j++;
}
next[i] = j;
}
}
这里构造的是每个值减一的next数组，如果不太明白，照着推一遍就好啦。
next数组是干什么用的呢？
| A | B | A | B | A | B | A | B | C | A | B | A | A | B |
| A | B | A | B | C | |||||||||
| A | B | A | B | C | |||||||||
| A | B | A | B | C | A | B | A | A |
蓝色区域就是一路匹配的过程，有没有发现绿色（忽略的部分）和 上一层的蓝色区域有什么相似的地方？把与后缀相同的前缀给略过了。
这样时间复杂度大大降低。
KMP算法和next的构造很相似
int kmpFind(String haystack, String needle) {
int[] next = new int[needle.length()];
nextBuilder(next, needle);
int j = -1;
for (int i = 0; i < haystack.length(); i++) {
while (j >= 0 && needle.charAt(j+1) != haystack.charAt(i)) {
j = next[j];
}
if (needle.charAt(j+1) == haystack.charAt(i)) {
j++;
}
if (j == needle.length() - 1) {
return i - j;
}
}
return -1;
}