简单易懂的理解 kmp 算法

KMP算法是一种字符串匹配算法，全称是克努特-莫里斯-普拉特算法。好吧，很长的一个名字，当然我们并不关心他的名字，我们要讨论的是该如何理解这个算法。这个算法理解起来有一点困难，尤其一些教科书。真的是上来就摔一脸数学公式，不少童鞋表示已经哭晕在厕所 T^T，往下看的勇气都没了，下面我们试试用简单的方式来理解他！

说到这，首选要知道KMP解决了什么问题！对于最简单的朴素的模式匹配算法(不了解的小伙伴自行百度)，他的效率并不高，后来为了加快效率，所以KMP诞生了！那么我们开始进入正题，首先看一个例子(图是小编绘的，原谅我的美术是体育老师教的)

如图，我们要在第一个字符串中找到第二个字符串，并且找到他的位置，我们首先按照朴素方式去匹配，我们发现，这两个字符串前面的a b c d e 都是一一匹配的，而第6个也就是g，与第一个字符串对应位置是不同的，如果这个时候按照朴素匹配的方法，我们应该是把第二个字符串，往后移一位，在继续比较，直到完全匹配为止。是不是感觉很累。。。但是通过观察，我们能发现一些有趣的东西。

首先，第二个字符串中，第一位a，与这个字符串其他位置的字母，都是不同的，而在第 6位之前的两个字符串所有字母都是一一匹配的，那么我们还有必要让a去一个一个的试6位之前的字母吗？很显然，完全没必要，这样，我们就可以让a直接移动到第6位去比较，我们省下了大把的时间，其实这就是理解KMP的关键，尽可能的在一次匹配失败后，往后面多移动几位，要知道，这样做可是要比朴素那样，笨笨的，每次往后只跑一个要快的多啊！

上面的第二个字符串，因为没有重复，所以我们很轻易的得到这个结论，但是，如果这个字符串有重复的，怎么办勒？我们看这个图

首先看图片里箭头上的部分(忽略图中数字，一会在讲)，在x字符串中匹配y字符串，我们观察发现y字符串中a是重复的。也就是说在y串中， 1和4位置的字母相同，而我们看图知道，在5位置之前，x和y字符串都是一一匹配的，那么x字符串在1和4之间的字母，也就是2，3，肯定是和a不一样的啊！那么既然不一样，我们肯定也就不能在傻傻的去比较了，把这些已经确定不会相等的位置跳过去，直接移动到相等位置，在匹配，也就是移动y字符串，使第一位置的a对齐第四位置，在继续比较。到这里不知道大家理解了吗！我们在补充说明一下，如果这个y字符串没有重复部分，那么他每次失败，就是往后走1个了！但是！！！如果有重复部分，那就要好好想想了！怎么样把重复部分和这个能往后走的位数定量联系起来呢？！我们可以看到图中有一行数字，这是什么呢？别着急，往下看！

首先我们引入一个变量j，他是y字符串的下标，从1开始，注意不是从0，有些算法表述是从0，但这里从 1。

我们把字符串每个位置对应的j值变化定义一个数组，叫做next[j]，图中数字其实就是next[j]数组对应的值。这个值怎么计算呢，我们用分段函数的形式，来定义一下，当j等于1时，next[1]＝0，当字符前缀与后缀不相同时，next[j]＝1。当j＞1且前缀与后缀有相同字符时，这里，我不写数学式子了，直接讲一下上图数字的计算过程，大家自己理解一下，首先，当j等于1时，为0，当j等于2时，1到j-1只有一个字符a，没有重复的，我们让这个值为1，再往下，j等于3和4同理，都是 1，当j等于5时，也就是1到4这段的字符是 abca，其中前缀a与后缀a重复了，所以是2，这里规则是这样的，有一个字母重复就是2，两个是3，三个是4。。。，总是多一个，比如 a b c a b d 这个字符串中，j＝6，也就是d，所对应的next[6]等于3，因为字符串abcab前缀ab与后缀ab是重复的，有两个字母，所以是3。

我们回到刚才的图，发现j等于5时，不相等，而next[5]＝2，所以我们让j＝2的字母来匹配，所以有箭头之下的图。这个2怎么理解呢， 在j＝5这个位置的前面的字符a，与前缀有一个相同的字母a，因为a与1-4之间的不同，但与4相同，所以让1跑到4的位置，之后比较1后面的也就是2来和x串5比较。这样总结下来，当next[j]＝k时，k-1为j前面相同的字母数量，k为前缀相同字母后的第一位不相同字母的下标，因为下标j是从1开始的，所以下一位的下标是2，如果有两个字母重复，则从前缀的第三位开始比较，他的下标就是3，注意，如果j下标从0开始，那么相同字母数量和下标是一样的，好了，到这里不知道你理解了吗！本文仅就KMP算法概念进行介绍，关于代码实现，可以参考其他资料！