前言

KMP算法是一种字符串匹配算法，该算法的思想主要是通过利用匹配失败的信息，从而减少字串与主串匹配次数，进而达到快速匹配的效果，简单来说，就是如果字串与主串匹配失败之后，我们不必再从字符串头去重新匹配了

KMP的核心思想

前面已经说了，KMP的核心思想是字串与主串匹配失败后，我们不必要再从字符串头去重新匹配，那么我们到底该怎么去实现呢？这就必须要说到next数组了，next数组其实就是前缀表

假如我们要进行下面这种匹配，也就是去判断主串AABAABAAC中是否包含子串AABAAC

• 一般做法

我们会从子串的头和主串的头依次去匹配，匹配成功则匹配下一个，如果匹配失败，那么子串整体后移一位，然后继续从子串的头去匹配，这样的效率是极其低的

• KMP做法

我们利用KMP算法去匹配字符串的话，匹配成功没什么好说的，匹配失败的话，他并不会去从头去重新匹配，而是通过前缀表找到需要重新匹配的位置，这样就能极大的增加我们的效率了

而在这里B和C匹配失败后，我们KMP算法的操作是不去从头去匹配，而是根据前缀表找到需要匹配的位置，然后去匹配

前缀表

根据上面，我们知道了KMP算法的核心就是前缀表，那前缀表到底是什么呢？

前缀表里面存放的东西是最长相等前后缀的长度，那究竟什么是前缀和后缀呢？

• 前缀

前缀指的是不包含字符串尾部的子串，例如AABAAC的前缀有A、AA、AAB、AABA、AABAA这五个

• 后缀

后缀指的是不包含字符串首部的子串，例如AABAAC的后缀有C、AC、AAC、BAAC、ABAAC这五个

为什么我们可以利用前缀表来实现回退呢？

首先我们需要明确一下，我们在KMP算法中，前缀表是基于子串来说的也就是例子中AABAAC，并非主串AABAABAAC。

因为前缀表对应位置的数字表示的就是：下标i前最长相等前后缀长度，当我们匹配失败之后我们只需要跳到匹配失败位置前一个字符所对应最长相等前后缀长度的位置

我们先求出next数组

A所对应的最长相等前后缀长度为0，因为只有一个字符，理论是没有前缀和后缀的

AA所对应的最长相等前后缀长度为1，AA的前缀分别为A，后缀也为A，所以最长相等前后缀长度为1

AAB所对应的最长相等前后缀长度为0，AAB的前缀分别为A、AA，后缀为B、AB，所以最长相等前后缀长度为0

AABA所对应的最长相等前后缀长度为1，AABA的前缀分别为A、AA、AAB，后缀为A、BA、ABA， 所以最长相等前后缀长度为1

AABAA所对应的最长相等前后缀长度为2，AABAA的前缀分别为A、AA、AAB、AABA，后缀为A、AA、BAA、ABAA，所以最长相等前后缀长度为2

AABAAC所对应的最长相等前后缀长度为0，AABAAC的前缀分别为A、AA、AAB、AABA、AABAA，后缀为C、AC、AAC、BAAC、ABAAC，所以最长相等前后缀长度为0

例子：AABAABAAC中是否包含AABAAC（思路及代码实现）

多说无益，我们直接进行代码实战

我们知道KMP的核心就是前缀表，也就是next的求解，我们先来求解next数组

    public static int[] next(String s){
        //需要返回的next数组
        int[] next = new int[s.length()];
        //左指针，指向前缀末尾位置
        int left = 0;
        //右指针，指向后缀末尾位置
        //后缀末尾位置，并不是我们认为的末尾
        //例如aab这个字符串的最长后缀为ab，他的后缀末尾为a，并非b
        for (int right = 1; right < next.length; right++) {
            //因为前缀末尾位置不等于后缀末尾位置所以需要回跳
            while(left > 0 && s.charAt(left) != s.charAt(right)){
                left = next[left - 1];
            }
            //相等的话就让左指针加一，然后给next数组赋值
            if(s.charAt(left) == s.charAt(right)){
                left++;
            }
            next[right] = left;
        }
        return next;
    }

因为我们知道单个字符没有最长相等前后缀长度，所以直接从1开始（ps：红色代表left，蓝色代表right）

我们看到此时left所指向的字符和right指向的字符相同且left为0，不需要left进行回跳，那么将left加一然后给next[1]赋值

然后进入第二次循环，right加一

此时left大于0并且left所指向的字符和right指向的字符不相同，那么进行回跳

然后此时left为0停止回跳，最终left所指向的字符和right指向的字符不相同，left不进行加一，这个时候给next[2]赋值

进入第三次循环，right加一

此时left所指向的字符和right指向的字符相同且left为0，不需要left进行回跳

然后此时left所指向的字符和right指向的字符相同，left加一，然后给next[3]赋值

进入第四次循环，right加一

此时left所指向的字符和right指向的字符相同，不需要left进行回跳

因为left所指向的字符和right指向的字符相同，left加一，然后给next[4]赋值

进入第五次循环，right加一

此时left所指向的字符和right指向的字符不相同，需要left进行回跳

仍然不相同并且left大于0，继续回跳

left为0，停止回跳，给next[5]赋值，循环结束

至此next数组已经构造完成了

然后我们就可以利用next数组进行字符串匹配了

仍然先放上代码

    public static boolean kmp(String a, String b){
        int[] next = next(b);//根据子串获取next数组
        int j = 0;//j指向子串
        //i指向主串
        for (int i = 0; i < a.length(); i++) {
            //j根据next数组进行回跳
            while(j > 0 && a.charAt(i) != b.charAt(j)){
                j = next[j - 1];
            }
            //如果相等那么j加一
            if(a.charAt(i) == b.charAt(j)){
                j++;
            }
            //如果j等于子串长度，证明已经走到末尾，匹配成功，返回true即可
            if(j == b.length()){
                return true;
            }
        }
        //匹配失败，返回false
        return false;
    }