KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)

其实很好理解，就是拿子串的和主串的第一位比较，然后往后比较，中间哪里比较失败了就从重新从第二位开始往后比较，如果失败了就从第三位开始往后比较：

在字符串X中寻找一个子串Y，当匹配到位置i时两个字符串不相等，这时我们需要将字符串f向前移动。常规方法是每次向前移动一位，但是它没有考虑前i-1位已经比较过这个事实，所以效率不高。

事实上，如果我们提前计算某些信息，就有可能一次前移多位。假设我们根据已经获得的信息知道可以前移k位，我们分析移位前后的f有什么特点。我们可以得到如下的结论：

前缀是指字符串的最前面n位和最后面n位。 比如：abcjkdabc，那么这个数组的最长前缀和最长后缀相同必然是abc。 cbcbc，最长前缀和最长后缀相同是cbc。 abcbc，最长前缀和最长后缀相同是不存在的。

注意最长前缀：是说以第一个字符开始，但是不包含最后一个字符。 比如aaaa相同的最长前缀和最长后缀是aaa。

KMP算法的思想就是在首先在字符串匹配的时候，如果已经匹配成功了一部分，当匹配失败的时候，不再从头匹配，而是从中间某一个地方开始匹配。 我们知道，如果子串和主串匹配了一部分，那么此时子串的最后一部分（后缀）肯定是和主串相同的。

如果说子串存在说，有前缀和后缀相同的情况（蓝色框框和红色框框），那么我们此时重新开始匹配的时候，就不需要从头匹配，而是拿相等的前缀和后缀，将子串的前面那部分对齐 （主串中和子串后面相等的那里（红色框框）） 因为前面这部分是相同的，我们只需要从后面再开始匹配就可以了。

先上代码，后做详细解析：

样例输入 3 qwertyuiop tyu aabbccdd ccc aaaabababac abac 样例输出 -1 0 0 5 -1 0 1 0 -1 0 0 1 8

首先要知道next数组怎么不靠代码，自己写出来： 首先初始化的时候，为了方便代码的书写，我们规定next[0]=-1 比如看j=2的时候，就看前面0-1位，没有相同的前缀和后缀，因此next[j]为0。 看j=3的时候，看前面0-2位，有相同的前缀和后缀，并且此时最大的前缀和后缀就是0和2，长度为1，因此next[j]为1 j=4的时候，看前面0-3位，有相同的前缀和后缀，并且此时最大的前缀和后缀是0-1和2-3，长度为2，因此next[j]为2，后续同理。

首先分析next数组的获得:

在这里，j和k代表一个子串中的正在比较的前后字符的位置，但是j只有往前移动或者不动 时候，如果匹配成功，我们需要让j和k都++，并且记录下此时k的位置，由于k是代表当前在哪个字符的下标，如果在下标1，然后又匹配成功，说明这时候最大前缀的长度是0j到1也就是2个，所以我们在存储next数组的时候需要对k++然后再存储。并且，我们的next数组，比如说next[6]，它是用来存放在第6个字符之前，也就是0-5的最大前缀是多少，因此当我们比如说判断完第1个字符和第5个字符相同，那么最大前缀长度是2对吧，这时候应该存放在next[6]里，因此j也要先++，然后才能把最大前缀长度存放进去，因此在这个循环中这两行语句的顺序至关重要：

但是如果匹配失败，这时候代表它不是我们想找的最大前缀和最大后缀，这个时候，首先j是不能移动的。 比如我们看这个： 比如现在运行到这里： 此时可以看到： 对于第五个字符来说，前面的字符串中，相同的最大前缀和最大后缀是aba，长度为3， 所以此时应在这里填下3（下面的截图中这里的3都忘记补上去了，请自行补上去，不过对于理解下面的片段来说没什么影响） ，好那么接下来需要匹配下一个字符，那么我们将k和j都后移 由于在上一次的判断中我们知道，之前是存在着最大前缀aba的，那么之后串的长度增加1了，有两种可能，一种是最大前缀的长度增加1，另外一种就是其他情况。 我们想知道最大前缀的长度是否增加1，只需要判断子串中新加入的这个字符，和原来最大前缀的后面一个字符是否相同即可：

如果相同，那么和上面一样，接下来将像之前所写的一样，j和k继续后移，如果不相同，我们就要找到新的相同的最大前缀和最大后缀了。那么此时的最大前缀的长度要么是3，要么比3小。

那么此时，我们需要判断相同的最大前缀和最大后缀的长度是不是3，如果不是3，那么判断是不是2，如果不是2，再判断是不是1。 但是显然这样的方法有点麻烦，由于我们知道，此时在k前面的，0-2的这个是之前所保留下来的最大前缀，而这里的next[k]也就是next[3]，所记录的是这个子串的最大前缀长度，也就是1（而最大前缀固定是从0号位开始的）那么对于这个子串而言，有最前1位和最后1位是相同的（0号和2号都是a）。

而我们知道，此时在j前面的3个长度的，也就是2-4，这个字符串和k前面的字符串(0-2)是一模一样的（前面得到的结论），那么意味着这个2-4的字符串也存在着最前1位和最后1位是相同的（2号和4号都是a）。

那么又由于这两个字符串相同，（0-2）和（2-4相同） 所以肯定，0-2的第1位和2-4的第1位也肯定是相同的：

因此，0-2的最前1位，和2-4的最后一位也是相同的。 也就是说，对于j前面的字符串（0-5位），我们已经有了第0位（第1个数字）=倒数第二个数字，那么如果说第1位（第2个数字）=最后一个数，那么最大前缀长度就是2了！

而本来j就指向最后一位了，我们只需要让k此时指向第2个数字，而非常奇妙的是！我们知道next[k]就代表前面的最大前缀的长度（这里长度是1），那么我们应该在最大长度的下一个数比较。 如果这里最大前缀长度是2，那么我们应该让k在第三个数与最后一个数进行比较，而我们知道在数组中，array[1]代表的就是第二个数字！

因此只需要让k=next[k]就可以实现了！

到这里不得不感叹看毛片 KMP算法的精妙啊。

那么到此为此就实现了next数组的构造。 接下来就需要实战了，实战用字符串来匹配子串的出现位置。

如果说子串或主串有一个已经走到了末尾，说明判断结束。

如果此时子串的j走到了尽头说明子串已经在主串中全部匹配成功，说明本次匹配成功，那么计算第一次出现下标的位置就是：

如果不是子串走到尽头而是主串走到尽头说明匹配失败，因此只需要用else，此处我们将结果返回0代表没找到

于是到此为止，就实现了看毛片算法，不得不说还是强的啊，想出这算法的人，简短又精妙。

补充一个图示匹配过程：