简单易懂的KMP字符串匹配算法（实现kmp字符串匹配）

什么是KMP

KMP算法是Knuth、Morris和Pratt三人设计的线性时间字符串匹配算法。算法的核心思想是尽可能地利用已知信息，减少尝试匹配的次数，从而降低时间复杂度。要想彻底地弄懂KMP算法，需要搞清楚几个概念，字符串前缀、后缀以及next数组。

字符串前缀和后缀

前面我们讲到，算法的核心思想是尽可能地利用已知信息，减少尝试的匹配次数，从而降低时间复杂度。那么如何利用已知信息，其涉及到字符串的前缀和后缀的概念，弄懂这两个概念是理解KMP算法核心思想的关键一步。

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

后缀是指不包含第一个字符的所以最后一个字符结尾的连续子串。

这两个概念有点不好理解，我们举个例子，以字符串abcd为例，其前缀集合为{a，ab，abc}，后缀集合为{d，cd，bcd}。

next数组

KMP算法利用已知的信息，减少尝试匹配的次数，从而降低时间复杂度。这里的已知信息其实指的就是next数组，利用next数组来回溯，从而不用从头开始匹配。那么next数组是从何推导出来呢？其实很简单，就是前面我们提到的字符串前缀集合和后缀集合中的最长的公共字符串的长度为值，匹配串中的子字符串的最后一个字符所在的索引下标作为next数组的索引下标构建出next数组。

举个例子，假设我们的匹配串p=ababaca，那么p的子串（包括其本身）集合为{a，ab，aba，abab，ababa，ababac，ababaca}。我们初始化next数组为int[] next = new int[p.length()]，也就是p串的长度作为next数组的长度。那么如何构建next数组呢？我们通过p的子串集合来构建。

子串a，此时没有前缀和后缀，其所在的匹配串p的小标是0，因此next[0]=0;

子串ab，此时是 前缀集合{a}和后缀集合{b}，前缀集合和后缀集合没有公共串且子串ab的最后一个字符b所在的匹配串p的下标是1，因此next[1]=0;

子串aba，此时前缀集合是{a，ab}和后缀集合是{ba，a}，前缀集合和后缀集合有公共串a，其长度是1，且子串aba的最后一个字符a所在的匹配串p的下标是2，因为next[2]=1;

以此类推，最终得到的next = {0,0,1,2,3,0,1}。

代码实现next数组

int[] longestPrefix(String p) {
        // 创建一个大小等于模式匹配串长度的表（使用数组表示）
        // table[i] 将存储子字符串p[0...i]的前后缀集合的最长公共串长度
        int[] next = new int[p.length()];
        int maxPrefix = 0;
        // 子串P[0]没有前后缀集合，长度是0
        next[0] = 0;
        // aac --> table = {0,1,0}
        // 对于其他的子串，我们有两种情况
        for (int i = 1; i < p.length(); i++) {
            // 情况1：当前字符不匹配最长前缀的最后一个字符
            while (maxPrefix > 0 && p.charAt(i) != p.charAt(maxPrefix)) {
                // maxPrefix > 0 表示找到了最长公共串
                // 如果这种情况，我们必须回溯，当前字符串(0,下标)的前一个字符串(0,下标-1)的
                // 最长公共串，如果我们到达了0，代表我们找不到匹配的字符
                maxPrefix = next[maxPrefix - 1];
            }
            // 情况2：最长前缀的最后一个字符与p中的当前字符匹配
            if (p.charAt(maxPrefix) == p.charAt(i)) {
                // 前后缀集合最长公共串的长度+1
                maxPrefix++;
            }

            next[i] = maxPrefix;
        }
        return next;
    }

KMP算法如何利用next数组

假设我们的匹配串p=ABCDABD，文本串s=BBCEABCDABHABCDABCDABDE，为了在文本串s中查找匹配串p，kmp算法是如何利用next数组呢？我们一步一步图解分析。

利用上文提到的longestPrefix函数，求得next={0,0,0,0,1,2,0}。为了在文本串s中找到匹配串p，我们使用双指针i和j，初始值都是指向下标0

通过逐个字符比较，当i=4，j=0时，找到了第一个匹配的字符，而后我们让i，j指针同时移动一位，即i=5，j=1继续比较下一个字符。只要指针i，j的字符匹配，我们就移动双指针一位，继续比较，当i=10，j=6时，字符不匹配了，即H !=D。

当字符不匹配时，next数组就派上用场了，利用它回溯，减少匹配次数。如果使用传统的朴素字符串匹配算法，此时我们都要移动i，j指针，重新开始匹配，即i=5，j=0，然后逐个重新匹配，增加了时间复杂度。

而KMP算法，利用next数组，此时指针i不变，只需移动指针j，那么指针j移动到哪个位置合适呢？我们知道子串t=ABCDAB是匹配的，此时next[t.length-1]=2,而j-1=t.length-1,所以实际编码时可以使用next[j-1]=2，这也就是j移动的位置了（匹配串p的下标）。此时i=10，j=2，相较传统的朴素比较算法，减少了匹配次数，降低了时间复杂度。

指针i=10，j=2时，继续比较，字符不匹配了，H != C，此时next[j-1]=0，因此移动下标到0，i不变，仍然是i=10.

指针i=10，j=0时，继续比较，字符不匹配了，H != A，此时j=10，说明前面没有一个匹配的字符了，需移动一位，即i=11，j=0。

指针i=11，j=0时，继续逐个比较，当i=17，j=6时，字符不匹配了，C != D。利用next数组，next[j-1]=2，因此移动j，即i=17，j=2，然后继续逐个比较。

当i=21，j=6时，字符匹配了，i和j都移动一位，此时j等于匹配串p.length，说明在文本串s中找到了匹配串p。如果要在文本串s中找到全部的匹配串p，只需移动j=next[j-1]，然后继续重复以上步骤比较匹配即可，这里不再赘述了。

KMP算法代码实现

按照上文图解，我们通过代码实现KMP算法，在文本串s中找出所有的匹配串p。

 List<String> kmpMatch(String str, String pattern) {
        int[] next = longestPrefix(pattern);
        List<String> matches = new ArrayList<>();
        // 文本串中的指针 
        int i = 0;
        // 模式串中的指针
        int j = 0;
        while (i < str.length()) {
            // 情况1 s[i] == p[j]，因为我们移动 i，j
            if (str.charAt(i) == pattern.charAt(j)){
                i++;
                j++;
            }else if (str.charAt(i) != pattern.charAt(j)) {
                // 不匹配了，如果我们至少找到了一个共同的字符，利用
                // next数组回溯
                if (j != 0){
                    j = next[j-1];
                }else {
                    // j=0,我们移动到下个字符，s[i+1]
                    i++;
                }
            }
            // 情况2：j与模式串长度相等，
            // 这表示我们到达了模式串的末端，也就是意味着
            // 我们找到了匹配的字符串了
            if (j == pattern.length()) {
                matches.add(str.substring(i-pattern.length(),i));
                j = next[j-1];
            }
        }

        return matches;
    }

总结

KMP算法相比传统的朴素匹配算法，之所以能够降低时间复杂度，提高性能，其实是利用了空间换时间的指导思想，即利用了next数组。在代码实现中，我们发现双指针i和j，i只会向前移动，而j会来回移动，但j不一定会移动到开始下标0位置，而是利用了next数组来确定其移动的位置，从而减少了匹配次数。