KMP算法的原理和实现

只要你学过数据结构与算法分析，相信你对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的精髓！

那么我们到底怎么样才能知道str2到底向右移动几位呢？又是怎么知道str2右移一位是不可能匹配成功的呢？我们还是首先回到第一轮的匹配中。我们已经说了，str2能够右移一位的前提是要下图中绿色两块的字符要全部匹配上，我们才右移动一位，不能再傻傻地无脑向右移动一位了。

那么在第一次的比较中，我们发现下标0~9范围内，str1和str2是全部匹配的，换句话说，str2中的绿色两块要完全匹配，我们才右移动！那我们怎么知道str2中的两块绿色是否完全匹配呢？这就又引出了一个KMP中的核心内容——前缀与后缀的最大匹配长度（也就是next数组）。

前缀与后缀的最大匹配长度

举个简单的例子，一个字符串abcabck，那么对于k字符来讲，它前面的字符串所构成的前缀与后缀最大匹配长度为3，如下图所示。

那么这玩意有什么用呢？回到刚才的例子

我们看一下str2相对于下标为10的字符前面的字符串所构成的前缀与后缀最大匹配长度是多少，按照上面的方法算一下，是5。

这就意味着，如果像刚才那样右移一位的话，那str2相对于下标为10的前缀与后缀最大匹配长度应该为9，但是现在只有5，所以右移一位肯定不能和str1匹配。

那么应该移动多少位呢？没错，就是5位。然后接着去匹配。

至此，关于KMP的大体思路已经讲解完毕，接下来的关键就是如何求出一个字符串中对于所有位置的前缀与后缀最大匹配长度。也就是我们常说的next数组。

如何求next数组

我们人为规定了next0=-1和next1=0，即0位置的前缀与后缀最大匹配长度是-1，而1位置的前缀与后缀最大匹配长度是0.现在我们假设要求i位置的前缀与后缀最大匹配长度，而现在又知道i-1位置的前缀与后缀最大匹配长度为7，那么，如果j位置的字符和i-1位置的字符相等的话，就可以得到i位置的前缀与后缀最大匹配长度为7+1=8.

如果i-1位置的字符和j位置的字符不相等的话，而我们又知道j位置的前缀与后缀最大匹配长度为3，那么我们就去看看k位置的字符是否和i-1位置的字符相等，如果相等，则i位置的前缀与后缀最大匹配长度为3+1=4。如果不等，则再继续以上操作，直到跳到0位置处，如果此时0位置还依然和i-1不等的话，那么i位置的前缀与后缀最大匹配长度为0。

以上这一段看着可能有点复杂，但是实际上很好理解，大家用纸和笔来画一下就清楚了！

下面是求next数组的代码

public static int[] getNextArray(char[] ms) {    if (ms.length == 1) {      return new int[] { -1 };    }    int[] next = new int[ms.length];    next[0] = -1;    next[1] = 0;    int i = 2; // next数组的位置    int cn = 0;    while (i < next.length) {      if (ms[i - 1] == ms[cn]) {        next[i++] = ++cn;      } else if (cn > 0) { // 当前跳到cn位置的字符，和i-1位置的字符配不上        cn = next[cn];      } else {        next[i++] = 0;      }    }    return next;  }

利用next数组进行字符串匹配行为

按照以上的思路，我们就可以利用next数组去执行KMP算法了，最终我们是要得到str2在str1全匹配的str1的下标位置，以下图为例，最终KMP算法是要返回8，因为str2是在str1的下标为8的位置处匹配上的，如果str2没有被包含在str1中，那么返回-1.

下面是利用next数组进行KMP算法的代码

// N >= Mpublic static int getIndexOf(String s, String m) {    if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {      return -1;    }    char[] str1 = s.toCharArray();    char[] str2 = m.toCharArray();    int i1 = 0;    int i2 = 0;    int[] next = getNextArray(str2); // O (M)    // O(N)    while (i1 < str1.length && i2 < str2.length) {      if (str1[i1] == str2[i2]) {        i1++;        i2++;      } else if (next[i2] == -1) { // str2中比对的位置已经无法往前跳了        i1++;      } else {        i2 = next[i2];      }    }    // i1 越界  或者  i2越界了    return i2 == str2.length ? i1 - i2 : -1;  }