如题，这道题可以用暴力解法直接秒了，但是时间复杂度为O(n×m)，n为主串的长度，m为模板串的长度

所以今天记录的是如何通过 KMP 算法来解，先给出 KMP 算法的时间复杂度 O(n+m)。高下立判了，有木有~~，不枉我费力的学习它（公司摸鱼时间）。

接下来从 KMP 算法有什么用、最长公共前后缀、前缀表/next 数组、怎么求前缀表 四个问题出发进行今天的学习记录与回顾。

一、KMP 算法有什么用？

开门见山，KMP 算法的最大应用场景就是字符串匹配。举个例子来说，我们有两个字符串，主串 s 以及模板串 t。现在我们要在主串 s 中去找有没有匹配 模板串 t 连续子串，在匹配过程中出现字符串不匹配的情况时，暴力的解法是放弃这一次匹配，从模板串 t 的起始位置重新开始匹配；而通过 KMP 算法可以知道之前在模板串 t 中匹配过的位置记录，这样就避免了从模板串 t 起始位置开始匹配了。

那么 KMP 是怎么记录这个以前匹配过的位置信息呢？答案就是前缀表，也叫 next 数组。

在介绍前缀表之前，先来理解什么是最长公共前后缀。

二、最长公共前后缀

最长公共前后缀要先理解什么是前缀，什么是后缀。

前缀：字符串中不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀：字符串中不包含第一个字符的所有以最后一个字符开头的连续字串。

在所有前缀和后缀中找到相同(公共)的最长子串，结果只有 jr 是两者共有的，那么最长公共前后缀为2。

理解了最长公共前后缀，接下来就是最关键的 前缀表！！

三、前缀表/next数组

还是举一个例子来说，主串为 oorojrjrjjrjr，模板串为 jrjjr。在拿主串去向模板串匹配过程中，在模板串下标为3的位置出现了不匹配，那么就求出下标0-2的子串（即 jrj）的最长公共前后缀长度为1，所以此时匹配跳到模板串 jrjjr 的下标1处开始匹配。

原理：下标为 3 之前这部分的子串（jrj）的最长相等的前缀 和 后缀 字符串是 子字符串 j，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面重新匹配就可以。

经过上面的例子，前缀表的求法也很清晰了，就是求不匹配字符之前的子串中最长公共前后缀。将结果放入到 next 数组中，每次出现不匹配，就去寻找该下标前一位的 next 数组的数值，就是要下次匹配的位置

四、怎么求前缀表？

在代码中如何实现，主要有三步：

1.初始化

2.处理前后缀不相同的情况

3.处理前后缀相同的情况

上代码：

//先获取 next数组
public void getNext(int[] next, String t){
        int j = -1;
        next[0] = j;
        for(int i = 1; i < t.length(); i++){
            //处理前后缀不相同的情况
            while(j >= 0 && t.charAt(i) != t.charAt(j+1)){
                j = next[j];//回退查看
            }
            //处理前后缀相同的情况
            if(t.charAt(i) == t.charAt(j + 1)){
                j++;
            }
            next[i] = j;
        }
    }

得到 next 数组后，开始主串与模板串的匹配，与求 next 数组思想一致，只不过 next 数组是自己（前缀）和自己（后缀）进行匹配，这里是主串和模板串之间进行匹配。

上代码：

public int strStr(String haystack, String needle) {
        //主串haystack,模板串needle
        int[] next = new int[needle.length()];
        getNext(next, needle);
        int j = -1;
        for(int i = 0; i < haystack.length(); i++){
            while(j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)){
                j = next[j];
            }
            if(haystack.charAt(i) == needle.charAt(j + 1)){
                j++;
            }
            if(j == needle.length() - 1){
                return (i - needle.length() + 1);
            }
        }
        return -1;
    }

这里有个注意点，如何判断在主串 s 中已经匹配完成 模板串 t 了呢？

如果 j 指向了模板串 t 的末尾，那么就说明已经匹配成功，将主串 s 中此时所匹配的字符下标 i 减去 模板串 t 的长度 再加 1，就是模板串在主串中出现的第一个位置。

完整代码如下：

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

    //先获取 next数组
    public void getNext(int[] next, String t){
        int j = -1;
        next[0] = j;
        for(int i = 1; i < t.length(); i++){
            //处理前后缀不相同的情况
            while(j >= 0 && t.charAt(i) != t.charAt(j+1)){
                j = next[j];
            }
            //处理前后缀相同的情况
            if(t.charAt(i) == t.charAt(j + 1)){
                j++;
            }
            next[i] = j;
        }
    }
}
上述内容代表这道题的 KMP 算法求解记录结束，除此之外，我还想再加一点内容。
我在网上看到了在蚂蚁25年春招-工程研发的实习笔试题中有一道这样的选择题：

在比对过程中，从oorojrj正常开始匹配，出现第一次的不匹配情况：主串的第8个字符为r，模板串的第4个字符为j，然后求出jrj子串的最长公共前后缀为1，所以跳到模板串的下标为1的字符r开始继续匹配，一直到结束，一共是7 + 1 + 4 = 12 次比较，主串长度为13，因此匹配效率为 12/13 ，答案选A。