1. 引言

KMP算法指的是字符串模式匹配算法，目的是在主串T中找到第一次出现完整子串P时的起始位置。该算法是三位大牛：D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的，以其名字首字母命名。在网上看了不少对KMP算法的解析，但是看了之后还是理解不够透彻，后来无意间刷到了一个讲解视频，感觉受益匪浅，瞬间通路了。在此感谢匿名大神，同时将视频地址也附在了文章末尾，各位可以看一下。

2.暴力解法

2.1 中心思想：双指针迭代，暴力求解

首先我们最直观想到的就是暴力解法，从左到右一个个匹配，如果这个过程中有某个字符不匹配，就跳回去，将T字符串向右移动一位。

初始位置.png

我们分别声明两个变量i、j分别指向T、P字符串的开始位置，开始遍历，对比T[I]=?P[j]，如果相等，则i++、j++往后对比，如果遇到不相等，例如下面：

不相等了.png
A和E不相等，那就把i指针移回第1位（假设下标从0开始），j移动到模式串的第0位，然后又重新开始这个步骤，如图：
再次重新开始.png

2.2 代码模版

class Solution {

    /**
     * 暴力匹配算法
     */
    public static int violenceMatch(String str1, String str2) {
        int i = 0;
        int j = 0;
        while (i < str1.length() && j < str2.length()) {
            if (str1.charAt(i) == str2.charAt(j)) {
                i++;
                j++;
            } else {
                j = 0;
                i = i - j + 1;
            }
        }

        // 结束条件是，P字符串遍历到末尾，证明已经找到模式串
        if (j == str2.length()) {
            return j - i;
        } else {
            return -1;
        }
    }
}

3.KMP算法

3.1 前言

首先我们思考，在上述问题中，如果求解过程中，人为去求解的话，肯定不会这样一次一次的直接返回去对比，而是在T[i]!=P[j]时，首先会直接跳过前面已匹配过的字符串，例如：

不匹配时.png

这种情况不匹配时，我们知道A、E不相等，可是我们可以看到字符串中有两个A-B-C字符串，我们可以直接跳转到如下情况，进行判断：

理想跳转png

对比面对上述不匹配的情况时，暴力解法 《》我们现在想要直接进行的跳转的区别是，i并未动，直接把j移动到了0，这是我们需要去思考一个问题，眼睛可以直接看到，我们可以这样去移动，但是代码如何去设计呢？这个规律是如何找到的？

3.2 最长公共前后缀

我们先了解一个概念，什么是最长公共前后缀？大家一定疑惑，为什么要去了解这个，我只能说，必须了解，这个是KMP的核心，我们先一起学习一下。

耐心.png

字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
举例：
如果一个字符串是ABCAB
那前缀集是{A,AB,ABC,ABCA}
后缀集是{B,AB,CAB,BCAB}
由此可知，此字符串的最长公共前后缀就是，AB

每个子串的最长公共前后缀长度.png

概念和书面的求法，我们都知道了，接下来面临一个难题， 这个代码应该如何去实现？

3.2.1 中心思想：DP

这时我们可以用DP的思想去思考一个问题，对于字符串{ABCAB}，可以分解为{A}、{AB}、{ABC}、{ABCA}、{ABCAB}，我们用int prefix[5]数组来保存每个子串的最长公共前后缀的长度，接下来我们将问题转换为，如何求取一个字符串的prefix数组？

求prefix.png
接下来我们举例，我们知道了，{ABCA}的最长公共字符串长度是len=prefix[3]=1，如图：
举例.png
则针对于{ABCAB}，只需去判断，P[len]]==P[i]，如果相等，则prefix[i]=len++，如果不相等，如图：
难道就是填0.png
难道就是直接prefix[i]=0吗？显然，不是这样的，因为还有以下情形：
等于1.png

针对于这种情形，prefix[i]=1，所以由上可知，我们针对于P[len]]!=P[i]的情形，我们应该再次分析一下，如果目前len>0，则将len退回上一个匹配字符的最长公共前后缀长度，即len=prefix[len-1]，如果len退无可退了，此时prefix[i]也只能等于0了。

image.png

3.2.2 代码模版

class Solution {

    /**
     * 求取prefix数组算法
     */
    public int[] getPrefix(String pString) {
        int[] prefix = new int[pString.length()];
        // 第一个字符的最长公共前后缀长度一定为0
        prefix[0] = 0;
        // 已知prefix[0],所以我们从第2个字符开始遍历
        int i = 1;
        // 代表prefix[i-1]的长度，由于prefix[0]==0，所以初始位0
        int len = 0;
        while (i < pString.length()) {
            if (pString.charAt(len) == pString.charAt(i)) {
                // 如果下一字符和之前pString[prefix[i-1]]相等，则prefix[i]=prefix[i-1]+1，i++，继续迭代
                len++;
                prefix[i] = len;
                i++;
            } else {
                if (len > 0) {
                    // 如果下一字符与之前pString[prefix[i-1]]不相等，则将len退回为上一个有效位置
                    len = prefix[len - 1];
                } else {
                    // 退无可退，代表当前i位置的最长公共前后缀没有，所以为0
                    prefix[i] = 0;
                    i++;
                }
            }
        }
        return prefix;
    }
}

3.3 KMP Search算法

由上面最长公共前后缀长度算法，我们求知匹配字符串P的 next数组，这个数组即为前面文章中提到的，T字符串的i指针不动，P字符串的j指针下一移动位置，每当T[i]!=P[j]时，这时，j指针不必要回归0，只需移动到prefix[j]位置，继续与i指针对于位置的T[i]元素对比即可，如图：

当i和j不匹配时.png
由于P字符串{ABCABB}的prefix数组为：
prefix数组.png
所以当T[i]!=P[j]时，此时j等于5，prefix[5]=2，所以j的下一个移动位置为2，如图
i不动，j移动到2.png

这里注意，要把prefix数组，后移一位，第一位置为-1

模版代码

    public void kmpSearch(String tString, String pString, int[] prefix) {
        int i = 0, j = 0;
        while (i < tString.length()) {
            if (j == pString.length()) {
                System.out.println("search index = " + (i - j));
                j = prefix[j];
            }
            // j==-1表示P字符串找到头了
            if (j == -1 || tString.charAt(i) == pString.charAt(j)) {
                i++;
                j++;
            } else {
                j = prefix[j];
            }
        }
    }