KMP算法一直让我们又爱又恨，难以理解却又效率很高。
看了看网上的KMP教程，无论是博客还是视频，大多以文字和逻辑推导的方式呈现，纷繁复杂，晦涩难懂。这会让我们在初学时多走很多弯路。
人类接受知识最直观的方式就是理解图像。于是我尝试用图解的方式详细解释一下KMP的原理， 最后通过例题加深巩固，达到完全学会的目的。
因为暴力匹配算法（BF算法）是学习KMP的前提， 因此，我们通过讲解BF算法，来引入KMP算法。
串的模式匹配的概念： 顾名思义，模式串B在文本串（主串）A中的查找过程，我们称为模式匹配。
解法一：暴力匹配算法 举个例子： 若给定文本串
BBC ABCDAB ABCDABCDABDE
和模式串
ABCDABD
现在要拿模式串去跟文本串匹配，整个过程如下所示： 首先，文本串的第一个字符与模式串的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。 因为B与A不匹配，搜索词再往后移。 就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。 接着比较字符串和搜索词的下一个字符，还是相同。 直到字符串有一个字符，与搜索词对应的字符不相同为止。 这时，我们需要将搜索词整个后移一位，在从头逐个比较。
经过多次循环， 我们总能成功匹配到对应的字串。
以上是暴力匹配算法的核心思想。
但与此同时： 一个基本事实是：当空格与D不匹配时，你其实已经知道前面六个字符是“ABCDAB”,而第二个字符B与目标串的第一个字符A是肯定失配的； 因此： KMP算法的想法是：设法利用这个已知信息，不要把“搜索位置”移回到已经比较过的位置，转而继续把它向后移，这样就提高了效率
怎么做到这一点呢？ 可以针对搜索词，算出一张部分匹配表，这张表是如何产生的，我们后面再做介绍，这里只要会用就可以了。 当空格和D不匹配是，前面六个字符“ABCDAB”是匹配的。查表可知，最后一个匹配字符对应的“部分匹配值是2”，因此按照下面的公式可算出向后移动的位数：
移 动 位 数 = 已 匹 配 的 字 符 数 − 对 应 的 部 分 匹 配 值 移动位数 = 已匹配的字符数 - 对应的部分匹配值 移动位数=已匹配的字符数−对应的部分匹配值
因为6 - 2 = 4 ， 所以将搜索词向后移动4位。 因为空格和C不匹配，所以继续向后移动搜索词，这时，已匹配的字符数为2（AB），对应的部分匹配值为0，所以移动位数为：2 - 0 = 2 ，向后移动两位。
因为空格与A不匹配，继续后移一位。 逐位比较，直到发现C与D不匹配，于是，移动位数 = 6 - 2 ，继续将搜索词向后移动4位。 逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索，移动位数 = 7 - 0 ， 再次将搜索词向后移动7位 ，这里就不在重复了。
下面介绍一下《部分匹配表》是如何产生的。
首先：了解两个概念：前缀和后缀 前缀指除了最后一个字符以外， 一个字符串的全部头部组合，后缀指除了第一个字符以外，一个字符串的全部尾部组合。 举例：字符串bread的前缀和后缀如图所示： "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。 以"ABCDABD"为例，
在这里，“部分匹配”的实质就是：
有时候，字符串的头部和尾部会有重复，比如：“ABCDAB”之中有两个AB，那么他们的“部分匹配值”就是2，也就是向后移动时， 第一个“AB”向后移动四位，（字符串长度-部分匹配值），就可以来到第二个“AB”的位置，大大提高了效率。
部分经典KMP例题：
HDU-2087HDU-2203HDU-1867HDU-3336HDU-6153HDU-3746HDU-4300看到这，你已经了解了KMP的原理，恭喜你，你成功的迈出了KMP学习的第一步！ 接下来，接连不断的AC掉10道以上的KMP类型题，你就在真正的掌握了KMP算法了。
如果这篇文章对你产生了帮助，就请给博主一个一键三连吧！有什么问题也可以在评论区留言指出。
