KMP 算法
- 整个过程主串指针 i 不会变小。
- 发生失配后，主串 i 不变，j=next[j]
- next[j]为前 j-1 个字符组成的子串中的最长公共前后缀中的前缀的下一个位置。
- next[j]=最长公共前后缀长度+1
- 最长公共前后缀不能是整个子串，比如”aaaa”的 next 数组为 0123
Tip
在匹配失败，j=next[j]之后，主串上一次匹配失败的位置开始重新匹配（也就是同一个位置还要再重新比较一次）。
KMP 算法的优化
优化思路：当 P[j]=P[next[j]]时，也就是模式串的当前位置和下一个跳转的位置的值相等，此时如果主串和模式串失配，那么跳转后必然会再次失配。为了减少比较次数，则将 next[j]更新为 next[next[j]]，重复递归，直到两者不相等。更新完后的 next 数组，跳转一次肯定不会出现相等的情况。优化完的 next 数组命名为 nextval。
kmp 算法的优化只是优化了 next 数组的结构，并没有修改原来的匹配算法。
求 nextval 数组时，一直递归到字母不相同为止。
示例
以”ababaaababaa”为例
next 数组为[ -1 , 0 , 0 , 1 , 2 , 3 , 1 , 1 , 2 , 3 , 4 , 5 ]或[ 0 , 1 , 1 , 2 , 3 , 4 , 2 , 2 , 3 , 4 , 5 , 6 ]
两种形式相差 1，这是因为原公式是 j=next[j]+1，为了方便计算，将 next 数组全部+1，则 j=next[j]，使得公式更加简洁。判断形式只需要观察 next 数组第一项是 0 还是-1 。
nextval 数组为[ 0 , 1 , 0 , 1 , 0 , 4 , 2 , 1 , 0 , 1 , 0 , 4 ]。
做题时还需要观察 j 的起始下标，一般为 next[1…n]，不过也有可能是 next[0…n-1]。