一篇读懂kmp

目录

一、kmp简介

二、如何加快匹配，提升性能

1）next数组的规定

 2）有了next数组之后如何加速

3）实例分析

 4）str1和str2中比较位置的跳跃

5）next数组值的填充

三、kmp时间复杂度分析

四、kmp代码实现

 ​

---

一、kmp简介

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) [1]  。

二、如何加快匹配，提升性能

1）next数组的规定

首先我们来介绍一下next数组，这个数组是针对str2（需要匹配的子串）而言的，next[i]的值是字符前最长相等的前后缀（前后缀不能取到字符串本身）。

 比如当前这个字符串aaaaak，对k而言，在他之前的最长相等前后缀长度就是4（aaaa和aaaa）

当然next[0]的位置就必须是-1（我们人为规定），因为它之前没有元素，next[1]的元素就一定是0，因为他之前只有一个元素，且前后缀不能取完。我们由此再练习一个字符串的next数组，一定要认识到next[i]和他本身的元素是没有任何关系的，只是取它之前的子串前后缀最大匹配长度！

 2）有了next数组之后如何加速

 假如我们str1和str2从i到x之前完全匹配（x和y不同），对原先的暴力匹配方法而言，我们str1比较元素需要跳到i+1，str2位置比较元素需要跳到0，只能用i+1位置元素和0位置元素进行匹配

对于暴力匹配而言我们存在如下过程

 需要比较的x跳回原先的i+1 y跳回原先的0

这样的比较无疑做了很多无用功，我们思考，如何最大限度减少比较次数呢？  

对于kmp算法而言，我们的x不需要进行回溯

我们此时让y跳回最大匹配长度前后缀的下一个元素（由next数组得到下标） 再与x进行比较，这样跳跃的实质是把str2往右推动，j和0一列

原先由i开头检查是否能配出完整的str2，现在实际上是由j开头检查是否能配出完整的str2

为什么可以往右推，推多少？

由于我们之前记录了最长匹配的前后缀，所以此时不经过比较我们也知道 j-x 是完全相同的，之前是比较的str2后缀，现在把前缀移动到后缀的位置，从可能出现不同的位置进行比较 我们把检查的位置由i移动到j，是因为我们知道i-j之间不可能配的出str2

3）实例分析

对于暴力匹配而言，我们在发现s！=z之后 需要对 i+1(b) 和 0(a）进行比较

对于kmp而言，str1比较的位置不冻，我们str2比较的位置由z跳向s，下一次比较的就是s和s，这样跳的实质其实就是我们在尝试以str1中j开头匹配出完整的str2 

为什么在i-j位置上不可能匹配出完整的str2呢?

我们假设i-j之间存在k开头可以匹配出完整的str2

 那么说明str1 k开头直到x和从str2 0开头等量的位置是一定相同的

由于str1和str2匹配到x和y才不同 所以对于str2他的后缀也一定是相同的

 那么此时问题就出现了，next【y】位置存的是最大的匹配前后缀，而此时str2 y之前明显存在更大的匹配前后缀，这和next记录的相互矛盾，所以i-j之间不可能匹配出完整的str2

 4）str1和str2中比较位置的跳跃

由于我们next【i】中存的是最大匹配前后缀在我们发现str2中y位置元素与str1匹配不相等时，我们就把y跳向前后缀相等 的下一个元素，也就是next【i】 

i1是str1中的指针  i2是str2中的指针

 如果i1位置元素等于i2位置元素，两个指针全部后移，但如果i2已经来到了0位置（i2 0位置的元素一定是-1）但还是i1和i2位置元素不相同，那么就只能i1后移，否则的话（i2还没来到0位置），那就把i2往前跳跃 i2=next【i2】

5）next数组值的填充

我们人为规定了next 0下标的元素是-1，1下标的元素是0，我们此时设想对next【i】位置进行填充

 我们此时已经知道next【i-1】的值，如果str中前缀的下一个元素（str[next[i-1]）和str【i-1】相等 那我们next【i】的值就为next【i-1】+1    如果不一样，就把str中下标为next【next【i-】】的值和str【i-1】进行比较，此次类推，直到无法往前跳，举个例子。

 如果i-1位置的元素和e相等，那么next【i】就应该是8+1  如果不等就从e开始往前跳，此时我们比较s和？

 s如果不等就再往前跳，next【s的下标】的值是0，我们此时比较a和？

如果a也和？不等，那么next【i】的值就是0.

cn的含义是用哪一个位置的字符去和str【i-1】进行比较，也是next【i-1】的值

三、kmp时间复杂度分析

我们假设主串长度是m 子串是n 在主串中没有回溯，所以时间复杂度是o（m）

在子串中

 我们对于i而言（已经填充的next下标）

三个if条件进行分析，发现它的时间复杂度是o（n）的，所以总的时间复杂度是O(m+n)

四、kmp代码实现

public class Solution {
    public int strStr(String haystack, String needle) {
       if (needle.length()>haystack.length()){
           return -1;
       }
       int i1=0;
       int i2=0;
       int[] next=getNext(needle);
       while (i1<haystack.length()&&i2<needle.length()){
           if (haystack.charAt(i1)==needle.charAt(i2)){
               i1++;
               i2++;
           }else if (i2!=0){
               i2=next[i2];
           }else {
               i1++;
           }
       }
       return i2==needle.length()?i1-i2:-1;
    }
 
    private int[] getNext(String needle) {
        if (needle.length()==0){
            return null;
        }
        if (needle.length()==1){
            return new int[]{-1};
        }
        int[] next=new int[needle.length()];
        next[0]=-1;
        next[1]=0;
        int i=2;
        int cn=next[i-1];
        while (i<needle.length()){
            if (needle.charAt(i-1)==needle.charAt(cn)){
                next[i++]=++cn;
            }else if (cn!=0){
                cn=next[cn];
            }else {
                next[i++]=0;
            }
        }
        return next;
    }
 
}