KMP算法（next数组的详细理解和leetcode题目）

KMP算法

1.应用场景

1.1 介绍：

KMP 算法（Knuth-Morris-Pratt 算法）是一个著名的字符串匹配算法，效率很高，但是确实有点复杂。

1.2 应用：

在实际生活中，字符串查找是非常常见的，在一段信息中匹配到你需要寻找的信息（就是在一段字符串找到需要匹配的字符串），那么怎样去寻找呢？

1.2.1 与寻常的暴力匹配寻找，它有怎样的优化

我们运用暴力匹配的时候，每次都匹配了很多此无意义的字符，什么意思呢？ 请看：

我们从这里开始匹配

因为主串【i】和匹配串【j】一直不相等，所以主串右移

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2FRshAuD-1600357474437)(en-resource://database/501:1)]

现在主串【i】和匹配串【j】相等开始匹配，i和j一起右移

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Du7rTIYl-1600357474439)(en-resource://database/503:2)]

现在它们又不相等了，所以

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-V7pWwAsB-1600357474440)(en-resource://database/503:2)]

按照暴力匹配的算法思想： 此时应该将i回溯，将i回到原来开始的位置的下一个位置，j归零。代码中的表现就是 i-(j-1)，j=0，但这样效率实在太差，我们已经知道关于字符串一部分信息了，我们怎样运用这部分加速匹配信息呢？这里就要用到
KMP算法了

2 算法思想介绍

算法简介

主要是消除了主串指针的回溯，之后效率就提高

加速匹配信息的介绍和提取

KMP 算法主要是通过消除主串指针的回溯来提高匹配的效率的，那么，它是则呢样来消除回溯的呢？就是因为它提取并运用了加速匹配的信息！
　　这种信息就是对于每模式串 t 的每个元素 t j，都存在一个实数 k ，使得模式串 t 开头的 k 个字符（t 0 t 1…t k-1）依次与 t j 前面的 k（t j-k t j-k+1…t j-1，这里第一个字符 t j-k 最多从 t 1 开始，所以 k < j）个字符相同。如果这样的 k 有多个，则取最大的一个。模式串 t 中每个位置 j 的字符都有这种信息，采用 next 数组表示，即 next[ j ]=MAX{ k }。

加速信息就是next数组

next数组

怎样优化

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KrNm9C2X-1600357474442)(en-resource://database/505:1)]

遇到像上图的情况怎样优化？

如果我们自己用人脑去思考，用眼睛去看：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-O6gQNGlt-1600357474443)(en-resource://database/507:1)]

到这里我们就可以得到了基本思路了，又该怎样去实现它呢？

next数组实现（语言层面）

实在不好描述，懂得都懂，因为我们现实生活比就是这样比，如果硬要描述，请看下面：

到了这里我们可以大概看出一点东西，当匹配失败时，j要移动的下一个位置k。存在着这样的性质：最前面的k个字符和j之前的最后k个字符是一样的。

如果用数学公式来表示是这样的

P[0 ~ k-1] == P[j-k ~ j-1]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xZ03Osc3-1600357474444)(en-resource://database/509:1)]

数学描述

当T[i] != P[j]时
有T[i-j ~ i-1] == P[0 ~ j-1]
由P[0 ~ k-1] == P[j-k ~ j-1]
必然：T[i-k ~ i-1] == P[0 ~ k-1]

前缀表描述

0 A
0 AB
0 ABC
1 ABCA（这里就是最大前缀A和最大后缀B）
2 ABCAB（类似：AB）
0 ABCABA（AB）

最大前缀和最大后缀的解释：比如ABCABA的前缀有{A,AB,ABC,ABCA,ABCAB}
最大后缀：{A，BA,ABA,CABA,BCABA}
这里解释下，因为自己最开始也理解不对

next数组的算法

在匹配串的每个位置都有可能发生不匹配，所以要计算没一个k（其实最后一个可以不算，但也可以，这里我们算，其实感觉不算更好）我们首先要知道next【j】=k,表示当它们不匹配时，j指针的下一个位置 （非常重要），还有就是，因为字符串是从下标0开始的，所以j位置之前的最大重复子串（最大相同前后缀），注意是j位置之前

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

记住最重要的东西：next数组中保存的是当它们不匹配时，j指针要移动的位置

2种情况（匹配和不匹配）

匹配

当它们匹配的时候怎么求next数组呢？这里我们可以发现用前缀表看出来

比如：ABAB
next【3】=1
next【4】=2
所以当它们匹配的时候就有：next【j+1】=next【j】+1

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bUPDEXTA-1600357474444)(en-resource://database/511:1)]

证明：
因为在P[j]之前已经有P[0 ~ k-1] == p[j-k ~ j-1]。（next[j] == k）
这时候现有P[k] == P[j]，我们是不是可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。
即：P[0 ~ k] == P[j-k ~ j]，即next[j+1] == k + 1 == next[j] + 1。
p为匹配串

不匹配

这里也是next数组最重要的部分

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RLXhTZjj-1600357474445)(en-resource://database/513:1)]

k=next【k-1】(我这里用的是k=next【k-1】，很多博客时用到的是k=next【k】，
因为我们求得是k位置之前的最大重复子串（最大相同前后缀，所以保存的位置可能不同，这和后面的一个解释也相互验证）

其实就是当k和j不相同的时候，就把k之前的字符串看做要匹配的串，后面的字符串看做主串，所以当它们不匹配的时候，就要和kmp算法的处理阶段一样，把它们移动到可能的地方.

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gUPwKaZY-1600357474446)(en-resource://database/515:1)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SdKrWbRm-1600357474447)(en-resource://database/517:1)]

其实可以用数学归纳法证明出来，
但解释语言比较长，现在天色已晚，后面有时间再补

KMP算法的实现

代码实现

class Solution {
    public int strStr(String haystack, String needle) {
                if("".equals(needle)){
                        return 0;
                }
           char[] noodleArr=haystack.toCharArray();
           char[] parmsArr=needle.toCharArray();
           int i=0;
           int j=0;
           int[] next=getNext(parmsArr);
           while(i<noodleArr.length && j<parmsArr.length){
                   if(noodleArr[i]==parmsArr[j]){
                           i++;
                           j++;
                   }else{ 
                           if(j>0){
                           j=next[j-1];
                           }else{
                                   i++;
                           }
                   }
           }
           if(j==needle.length()){
                   return i-j;
           }else{
                   return -1;
           }
    }
    public int[] getNext(char []parm){
          int[] next=new int[parm.length];
          next[0]=0;
          int k=1;
          int j=0;
          while(k<parm.length){
                  if(parm[k]==parm[j]){
                          next[k++]=++j;
                  }else{
                          if(j>0){
                                  j=next[j-1];
                          }else{
                                  next[k++]=j;
                          }
                  }
          }
          return next;
  }
}

一些对代码的补充说明

因为一些小细节的实现可能和其他博客不一样，所以特此进行说明

1. 首先我并没有把next【0】=-1

造成的结果是：
我的next数组每个位置保存的是当前位置的最大重复子串。但每次不匹配的时候，
要移动到的位置就是不匹配位置k之前的最大子串长度 （注意是k之前）
所以我的是k=next[k-1]

2.下面这段代码的一些小细节：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-N8cGPMF1-1600357474448)(en-resource://database/519:1)]

最开始我是这样写的（注意划红线的地方）
if（j>0）{
j=next[j-1];
}else if(j==0){
i++;
}

最开始真的没仔细思考，没想到当j=next[j-1]=0，之后造成了又进去了一次，其实这次完全是没必要的，这里就是当j=0时，i++，就是当它们一开始（i=0，j=0）就不匹配的时候，

下面是leetcode不符合的情况

一些知道情况的错误

1. [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hV19TSXv-1600357474449)(en-resource://database/521:1)]

这就是上面代码说明中的第2种情况

2. [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-37v8Hb0h-1600357474450)(en-resource://database/523:1)]

这是没考虑当要匹配的字符串长度为0的情况

一些不知道情况的错误

自己也一脸蒙蔽，当时也没处理（debug）因为其他事耽搁了

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7VlbGtoZ-1600357474451)(en-resource://database/525:1)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IDmIHTXK-1600357474451)(en-resource://database/527:1)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pzTm2IB1-1600357474453)(en-resource://database/529:1)]

KMP时间复杂度

建设字符主串的长度为m，模式串为n

有了代码过程就很容易得到时间复杂度 我们得到结果的条件是，字符主串或者模式串读完（注意是读完，不是读到）结尾，所以很容易就知道是O(N+M)

leetcode题目

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PcfcmrfM-1600357474454)(en-resource://database/531:0)]

思考和问题

为什么我用kmp算法表现还差些？是它用测试用例很极端吗？

暴力算法：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gqeBkCt9-1600357474455)(en-resource://database/533:0)]

KMP算法：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-u3KCu6Rz-1600357474456)(en-resource://database/535:0)]

这个题目还有个捷径：直接用Java的内置函数（indexof（））

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OmFPGQwY-1600357474456)(en-resource://database/537:0)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oEj3jny7-1600357474457)(en-resource://database/535:1)]

问题：

1. 发现自己对Java基础知识（比如集合）有点遗忘啊（过度依赖idea的提示功能了）
2. 自己应该以计算机的方式去思考