最近刚好学到了kmp算法，对我来说还蛮难的，原理还好理解，就是next数组的求解让我很懵
旁听了一下隔壁班大佬的分享，觉得他们讲得特别好，就想来记录一下
最长公共前后缀kmp算法首先要找“最长公共前后缀”，其定义为：A的“最长公共前后缀”是“A中以最后一个字符结尾的非前缀子串”与“A的前缀”能够匹配的最大长度。例：ababab我们从“最大长度”6开始向下枚举若答案是6。根据定义，“A中以最后一个字符结尾的非前缀子串”是ababab？我们注意到，ababab也算它自身的一个前缀因此，在枚举时，要从这个字符串的长度减一开始枚举！
若答案是5，则“非前缀子串”为babab。而“前缀”是ababa。两者不相等。
若答案是4，则“非前缀子串”为abab，而“前缀”是abab。两者相等。所以我们可以确定，字符串”ababab”的“最长公共前后缀”长度为4。
有什么用？举例说明：有两个字符串
S: abaacababcacT: ababc首先，根据最长公共前后缀，我们写出T串的所有前缀的“最长公共前后缀”长度：T[0~0] = “a”，最长公共前后缀长度：0T[0~1] = “ab”，最长公共前后缀长度：0T[0~2] = “aba”，最长公共前后缀长度：1T[0~3] = “abab”，最长公共前后缀长度：2T[0~4] = “ababc”，最长公共前后缀长度：0我们把求得的这5个数记为X数组（因为它还不是next数组）
这个更改后的X数组就是next数组，下图是上面的执行
next数组的含义是：当S[i]和T[j]不相等，并且j不等于-1时，j指针该指向的位置，且i指针不动。
当然我们目前只是枚举，接下来如何用算法实现求next数组
求next数组假设一个新的字符串R: a b c a b d e a b c a b c fnext: -1 0 0 0 1 ？我们要求next[5]
情况一 R[i-1] == R[next[i-1]]比如R[5-1]=R[1]，所以显然next[6]=next[5]+1=2
情况二 若R[i-1]!=R[next[i-1]]
R: a b c a b d e a b c a b c fnext: -1 0 0 0 1 2 ？我们发现R[i-1]和R[next[i-1]]并不相等。
用肉眼可以看出，我们在abcabd不管怎么取后缀，后缀的最后一个字符d，从来就没有在前面出现过。所以它不可能和任何一个前缀相等。所以next[6]才是0。
假设我们求到了这种程度R: a b c a b d e a b c a b c fnext: -1 0 0 0 1 2 0 0 1 2 3 4 5 ？发现R[2] == ‘c’。换言之，枚举next[13]时，我们发现6不行，5不行，4不行，其原因都在最后一个字符’c’不是前缀的最后一个字母。刚才我们发现R[next[12]]，也就是R[5]，和这个最后一个字符是不一样的但是，R[next[5]] = R[2] = ‘c’就和R[12]是一样的。也就是说，R[12] == R[next[next[12]]]。这不是巧合。可以证明，只要找到了这个’c’，且next[next[12]]=2，则R[13]就是2+1=3。并且可以证明，除了next[12]+1，next[next[12]]+1，next[next[next[12]]]+1…以外，next[13]不会有其他的答案了。只要多次迭代，就能求出next[13]。经过多次迭代，如果发现迭代到了-1这里还没有找到最后一个字符，那么我们直接让next[13]=-1+1=0就可以了。这也是我们让那个X[0]=-1的又一个原因。
总结
这就是求整个next数组的详细过程了，匹配的过程大家应该都懂，就不说了。