KMP 算法 简析

字符串匹配算法，这里只做简要分析。
看了网上一些文章，但有些图很多，但我越看越懵TT。所以总结一篇尽量没有图的。
要理解这个算法，要分两步。

1. 主串t与模式串p的匹配。
2. 匹配过程中使用的提前处理获得的next数组。

下面对这两步简单分析。

步骤一. 主串与模式串的匹配。

一些文章侧重点在求next数组，但个人觉得串的匹配这一逻辑才是真正的核心，所以先看这个。
如下两个串（*代表主串未知长度字母）：
主串T：****ababccc****
模式串P：ababe
此时匹配到串P的第五位，发现不匹配，比较笨的方法是串P后移一位，再从头比较。
如果此时，主串指针为i，模式串为j，那么就是i左移了j-1位，变成i - j + 1， j左移j位，变成0,再重新比较。
但是i和j同时回退显然没必要，之前的元素都已经知道比较过了啊，那么i可不可以不回退呢？
假设这个合理，i不回退，j回退变成了小于j的k，那我们继续比较T[i]和P[k]就行了。
那么势必要满足：

1. i之前的元素和k之前的元素能匹配上切k!=j.
2. 因为模式串的指针在当前元素不匹配的情况下会越来越小，所以k应该在满足条件1的情况下尽量大，防止我们漏掉某种匹配的情况。
3. 当然也有可能没有符合条件1的k，这种情况下直接i++，j = 0，再继续匹配就行了。我们设定这种情况k = -1

那么，当T[i] != P[j]时，我们直接移动j到k，继续比较T[i]和P[k],这个j和k的对应关系，就是所谓的next数组。为什么j和k可以一一对应以及next数组的求法在当前步骤我们完全不管，就假设已经有了这么个数组了，且next[j] = k;

那么按照上面的逻辑，我们写一下kmp算法，就很简单了：

public int kmp(char[] t, char[] p){
  int i = 0;
  int j = 0;
  int[] next = new int[p.length];//next数组的求法先不看
  while(i < t.length && j < p.length){
    if(j == -1 || t[i] == p[j]){ //j = -1就是我们上面说的情况3
      i++;
      j++;
    }else{
      j = next[j];
    }
  }
  if(j == p.length){
    return i - j;
  }else{
    return -1;
  }
}

下面我们按照刚刚提到的 k 要满足的几个条件来求这个next数组。

步骤二.求/验证next数组

再复制一下刚才的话：

主串T：****ababccc****
模式串P：ababe
主串指针i，模式串指针j，模式串目的指针k。
条件1：i之前的元素和k之前的元素能匹配上。

不难发现，当匹配到i/j时不匹配时，说明前面的字符是匹配的（废话。。。），条件1也就转成了和主串无关的: j之前的元素和k之前的元素能匹配上。

注意这里用到匹配这个词，因此，求next数组，就变成了模式串自己匹配自己的过程。
既然都是匹配，那逻辑自然和步骤1中的逻辑差不多，只不过目的不同。

1. 初始next[0] = -1,这个回看步骤1可以理解，这里不赘述.
2. 当P[j] == P[k]时，j+1之前的元素和k+1之前的元素能匹配上,next[j + 1] = k + 1,同时两个指针3都可以后移。
3. 虽说我们这里也是匹配，但肯定不能求出一个next[m] = m的结果啊，这不死循环了么。为了确保next[m] < m,我们k指针的初始设为j-1 = -1；
4. 当P[j] != P[k]时，应该怎么办呢？回看最上面的步骤1啊，k回退成next[k]后再做比较不久行了么？什么，步骤一里面没有提供这个next数组的方法？下面我们分析一下看看是不是真的没有。
   a. P[j] == P[k]时 j和k同时+1且可以计算出next [j+1]，而不匹配时k左移，所以说明再任何情况下，k<= j.
   b. 模式串和主串都是同一个，说明此时我们正在计算的next数组，就是上面我们需要的next数组啊，而我们所需要的next[k],上面的条件a说明我们已经计算出来了，因此求next数组的逻辑就是一次动态规划，直接拿来吧你！
   所以，步骤二我们求next数组直接抄袭步骤一稍作修改即可

public int[] getNext(char[] p){
  int j = 0;
  int k = -1;
  int[] next = new int[p.length];
  while(j < p.length - 1){
    if(k == -1 || p[j] == p[k]){
      next[++j] = ++k;
    }else{
      k = next[k];
    }
  }
  return next;
}

到这里，我们的next数组就求出来了。
那么，这个数组是否有优化的空间呢？

步骤三.next数组优化

这一部分我参考了一篇大佬的文章：https://www.cnblogs.com/dusf/p/kmp.html
归根结底，我们计算next数组是为了匹配字符串，如果当前两个字符不匹配，通过next数组修改j指针为k后，发现P[j] == P[k],那么P[k]和T[i]不还是不匹配么，害得再跳。而这种情况在我们计算next数组时就可以避免。因此上面求next数组的代码可以优化下：

public int[] getNext(char[] p){
  int j = 0;
  int k = -1;
  int[] next = new int[p.length];
  while(j < p.length - 1){
    if(k == -1 || p[j] == p[k]){
      if (p[++j] == p[++k]) { // 当两个字符相等时
          next[j] = next[k];//提前帮你跳了，省的匹配的时候不符合在跳，而k<j,所以这个next[k]已经是计算好的了，不会再出现p[j] == p[next[k]]的情况了。
      } else {
          next[j] = k;
      }
    }else{
      k = next[k];
    }
  }
  return next;
}

到此为止，感谢～