KMP算法

什么是KMP算法

KMP是三位大牛：D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的。
KMP算法要解决的问题是在字符串中找到模式串的位置。平时常见的关键字搜索，模式串就是关键字，如果它在一个主串中出现，则返回它的具体位置，如果不存在就返回-1。

例子

例如要在主串ABCABCABDJK中找到模式串ABCABD的位置。

模式匹配的暴力求解

• 看到这个问题，一个很直观的思路就是逐一比对，相同则继续比较下去，不同则错一位重复比对操作。

  
  

  当比较到C != D时，令主串的下一个元素作为头继续和模式串比较。暴力求解的时间复杂度是O(n * m)

• 从我们人的角度来看，我们估计会直接将主串和模式串以下图这样对齐然后比较。

直接就跳过很多步了，而这正是KMP算法要做的。

KMP算法求解

在讲KMP算法之前，先讲一讲字符串的前缀和后缀。
例如字符串ABCABD，规定前缀不能包含最后一个字符，后缀不能包含第一个字符。那么字符串ABCABD的前缀有A，AB，ABC，ABCA，ABCAB；后缀有BCABD，CABD，ABD，BD，D。最长的前后缀相等的字符串就是AB，因此称2为字符串ABCABD的最长前缀后缀。

• 在进行字符串匹配前，需要算出模式串中以每个字符结尾(不包含当前字符)的next数组，该数组表示以当前字符结尾的字符串的最长前后缀长度。
  以字符串ABCABD为例，
  定义一个next数组，int[] next = new int[5]
  • 以A结尾，next[0] = -1
  • 以B结尾，那就是A的最长前缀后缀，next[1] = 0
  • 以C结尾，那就是AB的最长前缀后缀，next[2] = 0
  • 以A结尾，那就是ABC的最长前缀后缀，next[3] = 0
  • 以B结尾，那就是ABCA的最长前缀后缀，next[4] = 1
  • 以D结尾，那就是ABCAB的最长前缀后缀，next[5] = 2
• next数组求解
  • next[0] = -1，next[1] = 0
  • i >= 2时，
    
    定义一个变量cn表示跳到的位置，如上图跳到的位置是cn = next[i - 1](i - 1位置最长前缀的下一个位置)
    如图，要求next[i]的值，我们要借助next[i - 1]的值，首先比较pattern[i - 1] 和 pattern[cn]，如果相等，那么显然next[i] = ++cn；如果不等，cn会往前跳，举个合适的例子如下图
    

如上图，pattern[cn] != pattern[i - 1]，那么cn会更新变成cn = next[cn]，变成下图位置

此时重复pattern[cn] 和 pattern[i - 1]的比较，显然pattern[cn] == pattern[i - 1]，则next[i] = ++cn。
(如果cn跳到不能再往前跳，next[i] = 0)

这个过程的代码如下

        next[0] = -1;
        next[1] = 0;
        int cn = 0;
        int i = 2;
        while(i < arr.length){
            if(arr[i - 1] == arr[cn]){
                next[i++] = ++cn;
            }else if(cn > 0){
                cn = next[cn];
            }else{
                next[i++] = 0;
            }
        }

• 有了这个next数组，我们就可以充分利用已经比较过的信息。
  接下来举个例子说明如何使用next数组的信息。

定义两个标记i和j，逐一比较，如果str[i] == pattern[j]，则i++,j++；如果str[i] != pattern[j]，那么就可以使用next数组的信息了，上图的位置str[i] != pattern[j]，j位置的最大前缀后缀为3，那么j就跳到3位置继续和str的i位置比较下去。特别地，如果刚好j位置是0，也就是next[j] == -1，即第一个位置就不匹配了，那么i指针后移一位，继续。
(循环条件：i < str1.length && j < pattern.length)