一文吃透KMP

⭐️前言⭐️

本文主要为了解决字符串匹配问题，在解决字符串匹配问题的方法中，最为出名的就是BF（暴力）解法和KMP解法，两者相比，前者更易理解但效率没有后者高。
本文通过先介绍BF解法，来为KMP解法做铺垫，使得两种解法都更易理解；一般题目中会涉及两个字符串，一个是文本串（haystack），另一个是模式串（needle），需要在文本串中找到模式串，如果找到了就返回模式串在文本串出现位置的下标，如果没有出现就返回-1.

以力扣题目【28. 找出字符串中第一个匹配项的下标】作为本文理解两种方法的工具。

🍉博客主页： 🍁【如风暖阳】🍁
🍉精品Java专栏【JavaSE】、【备战蓝桥】、【JavaEE初阶】、【MySQL】、【数据结构】
🍉欢迎点赞 👍 收藏 ⭐留言评论 📝私信必回哟😁

🍉本文由 【如风暖阳】 原创，首发于 CSDN🙉

🍉博主将持续更新学习记录收获，友友们有任何问题可以在评论区留言

🍉博客中涉及源码及博主日常练习代码均已上传码云(gitee)、GitHub

---

🍅1.BF（暴力）

如上图所示，需要在文本串：a a b a a b a a f a 中找模式串a a b a a f的出现下标，再依次匹配的过程中，BF解法就是如果遇到不同的字符，就需要让文本串的指向回退到开始匹配下标的下一个位置，模式串回到起点。

如果，模式串的指向走到了最后，说明找到了该模式串，返回文本串指向下标-模式串长度所对应的下标。
代码如下：

class Solution {
    public int strStr(String haystack, String needle) {
        if(haystack==null||needle==null) {
            return -1;
        }
        int i=0;
        int j=0;
        while(i<haystack.length()&&j<needle.length()) {
            if(haystack.charAt(i)==needle.charAt(j)) {
                i++;
                j++;
            }else {
                i=i-j+1;
                j=0;
            }
        }
        if(j>=needle.length()) {
            return i-j;
        }
        return -1;
    }
}

这种方法虽然可以跑过，但是其时间复杂度为O（M*N）(M、N分别为两个字符串的长度)，效率很低，下边这种KMP算法的效率更高。

🍅2.KMP

2.1铺垫

在BF解法中，因为文本串和模式串在遇到不同字符时，回退的太多了所以才导致时间复杂度太高，而KMP就是通过一些方法，使得文本串指向不回退，模式串指向回退一部分，这样两个指向的回退都减少了，避免从头再去做匹配了，从而优化提高了效率。

我们了解KMP算法的关键，就是了解清楚在这种算法下，指向回退的规则，在了解这个回退规则之前，我们来先认识一下最长相同前后缀

字符串的前缀指不包含最后一个字符的所有以第一个字符开头的连续字串，后缀指不包含第一个字符的所有以最后一个字符结尾的连续字串。

最长相同前后缀就是指从第一个字符开始到现在，相同前后缀的最大长度，可能还比较抽象，下边用这个图来辅助解释一下。

下边的数组就表示从第一个字符到当前字符最长相同前后缀的长度，举几个例子：下边为1的最长相同前后缀就是“a”，所以其长度为1；下边为2的最长相同前后缀不存在，所以为0；下标为4的最长相同前后缀为“aa”，所以其长度为2.

如果我们知道了模式串每个位置的最长相同前后缀，我们就可以知道模式串的指向该如何回退：

因为文本串与模式串的匹配是一步一步同步后移的，如果遇到不匹配时，不匹配字符的前边的字符串一定是相同的，知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

模式串与文本串不匹配字符的前一部分字符串一定是相同的，通过模式串的最长相同前后缀，就能得知模式串的前缀最长有多少与文本串的匹配最后部分是相同的，这样让文本串的指向跳转到前缀的后边，就能尽可能的减少无效的指针回退。

在遇到不匹配时，文本串指向不回退，模式串指向回退到前一个next[]位置所存储的位置

这个数组其实就是KMP算法的核心，也就是传说中的next[]数组，现在我们知道了它是怎样求出来的，下边我们来通过代码来计算它：

2.2构造next[]数组

构造next[]数组就是通过代码计算每个位置的最长相同前后缀，主要有以下三步（参考于《代码随想录》）
1.初始化
2.处理前后缀不相同的情况
3.处理前后缀相同的情况

1.初始化：
定义两个指针i和j，j指向前缀末尾位置（j不仅指向前缀末尾位置，也是相同前后缀的长度，结合3），i指向后缀末尾位置。

然后还要对next数组进行初始化赋值，如下：

int j=0;
next[0]=j;

一开始前缀的末尾位置就是0下边，next[0]如果不匹配也需要回退到j位置就是0下标。

2.处理前后缀不同的情况：
因为j初始化为0，那么i就从1开始，进行s[i]与s[j]的比较。
所以遍历模式串s的循环下标i要从1开始，代码如下：

for(int i=1;i<s.size();i++) {
}

如果s[i]与s[j]不同，就需要向前回退，next[j]记录的是j（包括j）之前的字串的相同前后缀长度，那s[i]与s[j]不同，就要找j前一个元素在next数组里的值（就是next[j-1]）。（其原因与之前2.1中的铺垫高亮部分理由相同，遇到了不相同的，那不相同的前边一小部分一定相同，就找前一个位置的最长相同前后缀，回退到前缀的后边再去比较是否相同，不相同再继续回退）
所以，处理前后缀不同的情况代码如下：

while(j>0&&s.charAt(j)!=s.charAt(i)) {
       j=next[j-1];
}

3.处理前后缀相同的情况：
如果s[i]与s[j]相同，那么就需要同时向后移动i和j，说明找到了相同的前后缀，同时还要将j（前缀的长度）赋给next[i],因为next[i]要记录相同前后缀的长度。

if(s.charAt(j)==s.charAt(i)) {
      j++;
}
next[i]=j;

最后，构建next[]数组的整体代码实现如下：

public void getNext(int[] next,String s) {
     int j=0;
     next[0]=j;
     for(int i=1;i<s.length();i++) {
        while(j>0&&s.charAt(j)!=s.charAt(i)) {
            j=next[j-1];
        }
        if(s.charAt(j)==s.charAt(i)) {
            j++;
        }
        next[i]=j;
     }
}

得到了next[]数组以后，就需要用这个来做匹配了。

2.3 使用next数组来做匹配

在文本串 （haystack）里找是否出现过模式串（needle）
定义两个下标j指向模式串起始位置，i指向文本串起始位置。

i从0开始，遍历文本串，如果不匹配j回退到前一个元素next数组存储的回退位置；如果匹配两者都后移；如果模式串遍历到了最后，说明完全匹配，返回匹配开始下标（i-j+1）；如果文本串遍历完了模式串还没遍历完，说明不存在，返回-1。

核心代码：

 for(int i=0;i<haystack.length();i++) {
     while(j>0&&haystack.charAt(i)!=needle.charAt(j)) {
         j=next[j-1];
     }
     if(haystack.charAt(i)==needle.charAt(j)) {
          j++;
      }
     if(j==needle.length()) {
          return i-j+1;
     }
 }
 return -1;

2.4 完整代码实现

class Solution {
    public int strStr(String haystack, String needle) {
        if(haystack==null||needle==null) {
            return -1;
        }
        int[]next=new int[needle.length()];
        getNext(next,needle);
        int j=0;
        for(int i=0;i<haystack.length();i++) {
            while(j>0&&haystack.charAt(i)!=needle.charAt(j)) {
                j=next[j-1];
            }
            if(haystack.charAt(i)==needle.charAt(j)) {
                j++;
            }
            if(j==needle.length()) {
                return i-j+1;
            }
        }
        return -1;
    }

    public void getNext(int[] next,String s) {
        int j=0;
        next[0]=j;
        for(int i=1;i<s.length();i++) {
            while(j>0&&s.charAt(j)!=s.charAt(i)) {
                j=next[j-1];
            }
            if(s.charAt(j)==s.charAt(i)) {
                j++;
            }
            next[i]=j;
        }
    }
}

---

⭐️最后的话⭐️

总结不易，希望uu们不要吝啬你们的👍哟(＾Ｕ＾)ノ~ＹＯ！！如有问题，欢迎评论区批评指正😁