只要你学过数据结构与算法分析，相信你对KMP算法应该都不陌生吧？如果你没听过，不要紧，今天我们就来聊一聊这个算法 。建议最好拿一张草稿纸，然后边看边理解，这样更有助于你对它的理解，更能理解它背后的精髓所在，相信你在理解完该算法之后，一定会大喊一声：妙啊！
KMP算法的诞生KMP算法是三位大牛：Knuth、Morris和Pratt同时发现的，于是取了他们名字的首字母然后组合起来，就成了该算法的命名 。
KMP算法要解决的问题就是查找一个字符串str2是否在另一个字符串str1出现过，也即str1是否包含str2这个子串，举个例子，可以看到下图，str1中包含有str2这个子串(aab) 。
文章插图
暴力解如果想要解决这个问题，我们很容易想到的一个算法是直接暴力遍历解，从左到右一个个匹配 。
文章插图
如果这个过程中有某个字符不匹配，之后我们只需要比较i指针指向的字符和j指针指向的字符是否一致 。如果一致就都向后移动，如果不一致，如图，i和j指针指向的字符不相等 。
文章插图
str2右移动一位，然后继续以上操作.
文章插图
直到遍历结束，最后匹配成功，可以返回str1包含str2.
文章插图
这种暴力的算法简单粗暴，可以解决该问题，其时间复杂度为O(M*N)，M为str1的长度，N为str2的长度 。KMP是对暴力解的一个优化，时间复杂度能做到O(M+N)，它的核心精髓是利用了以前的比较信息，然后推断此次比较 。说起来有点抽象，继续举个例子 。
KMP算法str1和str2刚开始按照从左到右遍历的顺序依次比较，发现到下标为10的时候，b不等于x，那么此时该怎么做？
文章插图
如果按照暴力的方法，是要将str2整个串往右移动一位，然后再次从左到右依次比较 。
文章插图
我们想一下，我们有没有必要将str2向右移动一位，然后再从左到右依次比较呢？如果有必要的话，那它的前提条件必定是下图中红色圈起来的两个范围全部匹配上！但是如果我们事先已经知道如果str2右移一位，然后红色圈起来的范围是不可能匹配成功的，我们就不需要让str2右移一位，而让str2右移若干位 。这就是KMP的精髓！
文章插图
【KMP算法的原理和实现】那么我们到底怎么样才能知道str2到底向右移动几位呢？又是怎么知道str2右移一位是不可能匹配成功的呢？我们还是首先回到第一轮的匹配中 。我们已经说了，str2能够右移一位的前提是要下图中绿色两块的字符要全部匹配上，我们才右移动一位，不能再傻傻地无脑向右移动一位了 。
文章插图
那么在第一次的比较中，我们发现下标0~9范围内，str1和str2是全部匹配的，换句话说，str2中的绿色两块要完全匹配，我们才右移动！那我们怎么知道str2中的两块绿色是否完全匹配呢？这就又引出了一个KMP中的核心内容——前缀与后缀的最大匹配长度（也就是next数组） 。
文章插图
前缀与后缀的最大匹配长度举个简单的例子，一个字符串abcabck，那么对于k字符来讲，它前面的字符串所构成的前缀与后缀最大匹配长度为3，如下图所示 。
文章插图
那么这玩意有什么用呢？回到刚才的例子
文章插图
我们看一下str2相对于下标为10的字符前面的字符串所构成的前缀与后缀最大匹配长度是多少，按照上面的方法算一下，是5 。
文章插图
这就意味着，如果像刚才那样右移一位的话，那str2相对于下标为10的前缀与后缀最大匹配长度应该为9，但是现在只有5，所以右移一位肯定不能和str1匹配 。
推荐阅读
- 喝生姜红茶减肥的注意事项,鲜牛奶润肤红茶
- 花草茶的营养成分及功能,几种易调配的花草茶
- 枸杞白茶的功效,枸杞茉莉花茶的宜忌人群都有哪些
- 为什么有的Excel文件无法打开？
- 杜鹃花茶的功效,桂花茶的功效和作用
- 五花茶的功效与作用,墨旱莲的功效与作用
- 我的电脑开机7秒，你知道是怎么做到的吗
- 陈皮洛神花茶怎么做,花茶的感官鉴赏
- 巨齿鲨是世界上最大的鲨鱼吗？
- 微商营销技巧有哪些？