KMP算法中next数组的理解

KMP算法解决了在字符串匹配过程中模式串指针回溯的问题，从而提高了字符串匹配效率。KMP具体细节在这里不展开讲，主要是梳理一下对KMP核心next数组的理解，要注意的是：目前网上有很多种版本的KMP算法，其next数组的定义也完全不同，因此，在学习KMP算法的时候，要先明确next数组的定义。

在本文中next[j]存放的是模式串P中P[0]到P[j-1]这个子串中，最长公共前缀和后缀的长度。

以上是next数组的构建代码，当时在学习KMP算法时，对下面这一操作不太理解，即当前后缀失配时，为何要按照此操作进行回退？

以下图为例：

现在我们知道了next[j]=6，那么怎么求next[j+1]呢？看下面的分析过程：

既然next[j]=6，这里我们记next[j]=k,在上图中，k对应等于6，也就是说t[0]...t[k−1]t[0] ... t[k-1]t[0]...t[k−1]和t[j−k]...t[j−1]t[j-k] ... t[j-1]t[j−k]...t[j−1]是对应相等的，也就是图上的两个蓝色条。注意到，t[j] = t[k]，也就是说，如果我们在两个蓝条后面都加一个相等的字符，那肯定也是对应相等的，这种情况最简单了，此时next[j+1]=next[j]+1。

我们再考虑 t[j] ≠ t[k] 的情况：

既然两个蓝色条对应相等，那我取其中的一部分，那也肯定是对应相等的，选取的依据就是next[k]的大小了，我们记next[k] = k’

也就是说，下图中①号对应的黄色条子串和②号对应的绿色条子串是对应相等的：

那么，我们现在只要比较t[j]和t[k’]（注意，这里是k’），也就是图中两个紫色的三角形，如果t[j]=t[k’]，则next[j+1]=k’+1;如果t[j]≠t[k’]，额，你还记得我们这种情况下是怎么进来的吗？不就是t[j]≠t[k]嘛！现在又来个t[j]≠t[k’]，而k’=next[k]，自然而然就会想到递归处理了，事实上，它们之间的确满足这个递归。至于递归退出的条件，就是next[0]这个边界值了。

以上便是j = next[j]的由来，参考博客。

更新，为保证思路的完整性，补充一下python的KMP完整代码：