KMP算法介绍参考KMP算法—终于全部弄懂了_June·D的博客-CSDN博客_kmp算法这篇博文。

在此基础上，我记录一些我的理解心路。

        1.首先是next数组的求解过程。当k == -1 或者 t[j] == t[k]时很好理解，就是当前j的next值就相当于j-1的next值再加一。而t[j] ！= t[k]的情况下，这时候将我们想找的最长公共前后缀分为前缀与后缀考虑：

        前缀是由j-1的最长公共前后缀的某个前缀加上这个前缀后面的一位字符组成

        后缀是由j-1的最长公共前后缀的某个后缀加上t[j]组成。

 

我们要让这个前缀与后缀相等，则第一件事就是要取j-1的最长公共前后缀的某个前缀等于同等长度的后缀，也就是让上面的前缀与后缀的第一部分相等，这即是j-1的最长公共前后缀的最长公共前后缀，这就是k=next(k)的来源。

        2.不同的KMP算法的实现对next的定义是可能有差别的。有的取最长公共前后缀长度为n的next值为n-1，有的为n。此外，有的KMP的next[j]值保存的是0~（j-1）的字符串的最长公共前后缀的长度，有的是0~j。但是本质都一样，只是变换时+1-1的区别。