对KMP算法中next数组的深入理解

这几天在练车，所以没有每天更新，主要是练车练得有点心累，前天就已经复习完字符串这一章了，但是一直拖到今天才把KMP算法真正地弄懂。下面进入正题：

首先了解kmp算法是干嘛的，它的作用是进行一个模式匹配，即在一个字符串中寻找是否存在某一个子串，比如在aabbccabc这个主串中是否存在abc这个模式串，并且输入他们匹配时，在主串的位置，如上例中，就应该输出的是“在第7个位置他们进行匹配”。 这就是kmp算法的作用。

kmp算法的最大特点是，它不用将主串中的已经匹配过的字符进行回退（这里是和经典算法进行比较，经典的匹配情况，我们大家应该都能想到，就是在两个字符串进行比对的过程中，主串第1位和模式串第1位比较，主串第2位和模式串第2位比较，依次类推，假设主串的第i位与模式串对应位置不匹配时，那么，经典的做法就是从主串的第二位开始，再与模式串的第一位进行比较。这样依次下去，时间复杂度为o（mn），即是一个积）而kmp算法，通过使用已经匹配的位置信息，来使时间复杂度减小到O（m+n）。而在kmp算法中最关键的就是next数组的计算。 下来给出我的思路：

next[j]=k,它的意思是，当模式串的第j位与主串的第i位失配时，这时主串的位置不回退，而是将模式串退到第k位，再次与主串的第i位进行匹配。 直到成功匹配，或者超出字符数量为止。

至于为什么要这样做，我就不详细说了，严蔚敏老师的书上讲的很清楚，我想讲一下next数组代码的具体实现：(纯手敲，训练感觉)

那么上面的while循环到底是什么意思呢？实际上，kmp算法其实就是在主串与模式串失配是，在模式串中，找到最大的相同前缀和后缀。怎样找呢？ 将模式串看成既是主串又是自己的模式串，

实际上，严蔚敏老师的书上已经说的很清楚了，用递归的思想来求，定义next[1]=0，我们假设next[j]=k,也就是说，第j位失配时，用第k位来进行匹配。那么第j+1位呢？有两种情况，一是当j=k时，显然，next[j+1]=k+1,二是当j!=k时，next[j+1]=next[k]+1。 看到这里不知道大家明白了没有，实际上，上面的while就是可以将这个递归的意思表达出来，至于while中为什么要加k==0,现在应该很清楚了吧，既然是递归，你必须要有一个初始条件吧，类比于数学归纳法。

**如果像上面那么说，还没懂的话，可以看看这段代码来源于这个博客

将next数组理解了之后，就很容易理解KMP算法本身了。

这里j==0，可以有两种理解，一是kmp算法的特性，二是用了next数组。

KMP算法总代码

实现示意图：