用通俗易懂的语言搞懂字符串匹配算法KMP（图片很多）
前戏
在大家平时编码的过程中，肯定会遇到比较字符串，这种场景经常会在我们的日常开发中经常碰到。为了更好的通俗易懂说明字符串匹配过程，我们先来看个例子吧，有一个字符串“BBC ABCDABABCDABCDABDE”，我们如何知道里面是否包含另外一个字符串“ABCDABD”呢？大家思考10秒钟，能否自己想到好的方式？
其实有很多算法可以解决这个查找的工作，Knuth-Morris-Pratt算法简称KMP是最常用的算法之一。之所以叫这个名字，是因为三个人发明了这个算法，就以他们名字的首字母表示这个算法。网上有很多文章讲解这个算法，但是都是不太容易去理解，那本文呢，就是用简单的语言描述，让大家能够快速理解KMP算法，多谢大家支持！
算法图解
我们来解释一个名字，
搜索词：我们需要判断的字符串“ABCDABD”
- 首先，第一步很简单就是比较第一个字符嘛，字符串“BBC ABCDABABCDABCDABDE”第一个字符“B”和搜索词第一个字符“A”比较，显而易见不匹配，所以接下去的操作是将搜索词整体后移一位。看下图：
- 然后呢？再比较第一个字符，发现还是不匹配，所以搜索词还得后移一位，直到能够匹配搜索词的第一个字符“A”为止。看下图：
- 接着就是比较搜索词跟被比较字符串的下一个字符了，结果很明显，匹配。看下图：
- 接着还是往下比较，什么时候停止呢？直到搜索词和被比较字符串对应的字符不匹配为止。看下图：
- 这个时候，怎么操作呢？当然很容易想到的一种方法就是讲整个搜索词后移一位，重新比较了。我只能说这种方式很好，可行。但是你想过没有，后移一位就会把位置移到已经比较过的地方了，重新比较一遍，看下图所示。有没有隐隐觉得这里可以优化？
- 当空格与D不匹配的时候，其实你已经知道前面的字符是“ABCDAB”。KMP的基本思想就是不要重复已经比较过的位置，可以大胆的向后移，这样不是可以提高搜索的效率了吗。
- 那怎么记录那些已经比较过了呢？可以针对搜索词，算出一张专业术语名称叫《部分匹配表》，那这张表又是如何算出来的呢？这个后面介绍，先况且知道它的用法就OK了。
- 那么已知空格和D不匹配，而且前面留个字符都比较过，匹配的。可以查表得出，最后一个匹配字符B对应的“部分匹配值”是2，我就用下面的公式算法算出向后移动的位数：移动位数=已匹配的字符数-对应表的部分匹配值，所以6-2=4，后移4位。看下图：
- 因为空格和C是不匹配的，所以还要继续往后移动。利用算法算出移动位数：2-0=2 。看下图：
- 同样的道理，后移。看图：
- 同样的道理，继续后移：6-2=4位。看下图：
- 最后惊喜的发现所有的都匹配上了，于是整个搜索过程就完成了。如果字符串够长，需要找出全部匹配，那也是同样的道理，移动位数：7-0=7位，这里不再赘述了。
可能很多童鞋会说，这张表的如果算出来的，还是没有讲，那接下来我们就来讲下《部分匹配表》的产生。
首先灌输大家两个概念：“前缀”和“后缀”。前者的意思是除了最后一个字符以外，一个字符串的全部头部组合；后者的意思是除了第一个字符以外，第一个字符串的全部尾部组合，如果还不能理解，自行看下图：
《部分匹配表》就是“前缀”和“后缀”的最长的公共元素的长度。如果还不能理解，请自行看下图：
个人理解，引入这张表的意义就是字符串的头部和尾部如果有重复，需要通过这种手段找出来，不让匹配的时候错过重复的部分。
总结
怎么样？童鞋们理解了吗，总结八个字就是“后移匹配，跳过重复”。今天的文章就到这里，谢谢大家支持，下期文章再见！