KMP算法

本文最后更新于：4 个月前

KMP算法

理论篇

前言

第一次接触KMP算法是在《大话数据结构》这本书上，算是这本书第一个有难度的部分，之后在B站上看了相关视频勉强弄了个半懂。

昨天在Leetcode上再次刷到了KMP——28. 找出字符串中第一个匹配项的下标，但是没法自己写出代码实现，于是又深入的学习了下如何手撕。

这下算是完全懂了，主要参考的是代码随想录对应题目的章节，这里我再按照自己的理解复述一遍。

什么是KMP？

KMP这个名字来自于发明这个算法的三位学者的名字首字母：Knuth，Morris和Pratt。

我还看到一个比较有意思的拼音解释，(K)快速(M)模式(P)匹配，用来形容这个算法再贴切不过了。

KMP主要解决了什么问题？

KMP主要解决字符串的子串匹配问题。

例如：查找字符串 "aabaabaafa" 中是否存在字符串 "aabaaf" 。

前一个字符串称为文本串，后一个字符串称为模式串。

遇到这样的问题，第一反应往往是双层for循环遍历两个字符串来查找是否存在这样的子串（暴力解法），如果文本串的长度记为 m ，模式串的长度记为 n ，则算法的时间复杂度为 O(mn) 。

暴力解法当然可以解决字符串匹配问题，Leetcode的28题也可以用这样的方法AC（Accept），但是有没有时间复杂度更低的算法呢？

KMP算法给出了答案，KMP通过记录已经匹配的字符信息，达到避免重复回溯指针的目的，使算法的时间复杂度能够降低至 O(m + n) 。

那么如何记录已经匹配的字符信息呢？通过next数组。

但在介绍next数组前必须先理清几个概念，何谓前缀？何谓后缀？何谓最长相等前后缀？何谓前缀表？

什么是前缀后缀？

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

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

例如，对于字符串 “abba” ：

其前缀为 "a" 、 "ab" 、 "abb" 。

其后缀为 "bba" 、 "ba" 、 "a" 。

什么是最长相等前后缀？

有了前后缀的概念，最长相等前后缀就很容易理解了。

最长相等前后缀的长度指对于某一字符串，它最大的相同前后缀长度为多少。

仍然以字符串 "abba" 为例，其最长相等前后缀为 "a"，最长相等前后缀的长度为1。（而不是2，因为子串 “ab” 不等于 “ba”）。

什么是前缀表？如何计算前缀表？

前缀表记录了模式串中当前下标位置之前的字符串（包括当前位置）的最长相等前后缀的长度数据。

光看这句话可能有点懵，下面以模式串 "aabaaf" 为例写一下它的前缀表。

下标	0	1	2	3	4	5
模式串	a	a	b	a	a	f
前缀表	0	1	0	1	2	0

首先将指针放置在第一个字符 "a" 上，此时下标为0，其 “当前下标位置之前的字符串（包括当前位置）” 为 "a" ，字符串 "a" 的前后缀都为空，因此最长相等前后缀为0，前缀表中下标为0的位置填入0。因此对于所有前缀表，其下标为0的位置都可以直接填入0；

之后将指针放置在第二个字符 "a" 上，此时下标为1，其 “当前下标位置之前的字符串（包括当前位置）” 为 "aa" ，字符串 "aa" 的最长相等前后缀长度为1，前缀表中下标为1的位置填入1。

依此类推，我们可以看着模式串将前缀表填写完整。

前缀表和next数组有什么关系？

这是个困扰了我很久的问题，因为不同的人对next数组有不同的讲法。

程杰在《大话数据结构》里给出的next数组和nextval数组我到现在都没看明白，各种考研辅导老师和视频里给出的next数组定义也很不统一，一会要整体右移并且第一个位置赋-1，一会要统一减一，绕的很晕。但是代码随想录的卡尔在他的文章和视频里解释的很清楚，我再在这里陈述一遍。

next数组可以就是前缀表本身，也可以是整体右移一位第一位赋值-1，还可以是整体减一。无论采用何种next数组都只是KMP算法实现细节，不涉及原理性的东西。

所以在这里我们选择使next数组即为前缀表本身，这种方法更接近KMP的实现原理（前缀表），更方便我们记忆。

next数组（前缀表）有什么作用？

到现在为止我们已经掌握了一项技能，就是看着模式串写出前缀表，即写出next数组。

next数组之所以叫next，是因为当文本串指针与模式串指针所指字符不匹配时，可以根据next数组回溯模式串指针到新的位置来继续匹配，而不必总是回到模式串头位置。

next数组（前缀表）为何能回溯模式串指针？

首先我们先看一下文本串 "aabaabaafa" 是如何查找模式串 "aabaaf" 的。

文本串指针和模式串指针分别从各自字符串的头部开始一一向后比较，前五个字符 "aabaa" 都能够匹配，此时移动到第六个字符发现不匹配。

到这一步，暴力（或称朴素）算法就要将文本串指针回溯到第二个字符，模式串指针回溯到第一个字符重新开始匹配了。

而KMP的模式串指针由 "f" 回溯至 "b"，而文本串指针不动等待继续匹配，KMP的优越性就体现出来了。

那么为什么模式串指针要从 "f" 回溯至 "b"呢？

下标	0	1	2	3	4	5
模式串	a	a	b	a	a	f
前缀表	0	1	0	1	2	0

以下这句话，对于理解为什么前缀表可以告诉我们匹配失败之后跳到哪里重新匹配，非常重要！

下标5之前这部分的字符串（也就是字符串 "aabaa"）的最长相等的前后缀是子串 "aa"，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面，并从这个位置重新匹配就可以了。

所以前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力。

但如果新的模式串所指字符依然与文本串指针所指字符不同又当如何呢？

那我们继续重复上述过程，当前模式串下标为2，查询 next[2 - 1] 的值为1，将模式串的指针回溯到下标为1的位置，即第二个字符 'a' 。

如果一直无法与文本串指针所指字符匹配（模式串指针指向下标0位），那么文本串指针向后移一位。

KMP算法匹配过程总览

这下我们大概了解了KMP的匹配过程，再来回顾一下：

首先我们需要根据模式串写出next数组（前缀表）。
之后我们让文本串指针i与模式串指针j同时从各自字符串头部开始向后遍历。
一旦遇到字符不匹配的情况我们根据 next[j - 1] 的值将模式串指针j回溯到对应的下标位置，而文本串指针i不做变化。直到找到新的能够匹配的模式串指针，则继续向后匹配；或者j回溯到0位也没有遇到能匹配i所指的字符，那么文本串指针i向后移一位（++i）重新匹配。
如果循环到某个位置，模式串的所有字符都匹配完成了，则表示能够在文本串中找到对应子串；反之，若文本串指针i走到文本串的末尾也没能匹配完所有的模式串字符，则表示不能在文本串中找到对应子串。

至此大功告成！

KMP算法的时间复杂度分析

如果文本串的长度记为 m ，模式串的长度记为 n。

在最差情况下（模式串在文本串的末尾才能被匹配），暴力的双for循环时间复杂度为 O(mn) 。

而KMP只需要遍历一次文本串O(m)和生成next数组O(n)，总的时间复杂度为O(m + n) 。

因此KMP算法可以极大地提高检索效率。

代码篇（C++）

前言

Leetcode上的题目 28. 找出字符串中第一个匹配项的下标是练习KMP代码的最佳实践，这里就从此题出发介绍KMP代码的实现。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回-1。

示例 1：输入：haystack = "sadbutsad", needle = "sad" 输出：0 解释："sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：输入：haystack = "leetcode", needle = "leeto" 输出：-1 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

KMP算法的代码套路

根据我们在理论篇 - KMP算法匹配过程总览中的介绍，实现KMP算法需要两个函数，其中一个用来计算next数组，另一个用来匹配模式串。

根据我的观察这两个函数的书写都有如下的固定套路：

初始化
处理两指针所指字符不等情况
处理两指针所指字符相等情况

在理解的基础上记住这三步走就能轻松手撕KMP。

getNext()函数的实现

void getNext(int* next, const string& s) {
    //初始化：next[0] = 0，j为前缀尾指针，i为后缀尾指针
    next[0] = 0;
    int j = 0;
    for (int i = 1; i < s.size(); ++i) {
        //处理两指针所指字符不同情况
        while (j > 0 && s[j] != s[i]) {
            j = next[j - 1];
        }
        //处理两指针所指字符相同情况
        if (s[j] == s[i]) ++j;
        next[i] = j;
    }
}

为什么选择返回类型为 void 的函数，并且多传入一个空的next数组？

因为C++不允许函数返回一个完整的数组，所以我的第一想法是返回指向next数组的 int* 指针，但如果这个指针指向 getNext() 作用域内的局部数组，那么当函数结束时，该指针将成为一个野指针，继续在外部调用这个指针可能会导致未定义行为（虽然我这样写了leetcode没有报错，但仍然不建议这么做）。

如果我们不想从外部传入一个next数组，那么还有两种方法：

一种方法就是在函数内部定义一个静态数组。但我们需要一个变量 s.size() 来确定静态数组的大小，C++不允许声明一个可变大小的静态数组，所以此方案不可行。
另一种方法是使用动态分配数组（ new int[] ），但这种方法有个缺点是需要在主函数（匹配函数）中手动回收内存（ delete [] ），会让主函数看起来很乱。

所以最好的方法还是在主函数中声明一个空next数组，之后通过指针传递到getNext()函数中。

可以在菜鸟学习更多C++从函数返回数组内容。

1. 初始化

在这一阶段我们初始化了两个指针，j为前缀尾指针初始指向下标0位，i为后缀尾指针初始指向下标1位；并且将next[0]初始化为0（首字符不存在相等前后缀）。接下来我们遍历后缀尾指针i，在不断地遍历中填充next数组。

2. 处理两指针所指字符不等情况

在这种情况下我们对 s[j] 和 s[i] 内容进行比较，发现两者不相同，那么前缀尾指针j就要回退，退到哪里呢？

我们回头看next数组， next[j - 1] 中所存储的数字表示从模式串头部到下标为 j - 1 的位置的字串的最长相等前后缀长度。那我们跳回到下标为 next[j - 1] 的位置，那么现在的新前缀尾位置 j = next[j - 1] 会和匹配失败时的前缀尾位置之前的字符串完全相同。

当然，有可能一次回退后 s[j] 与 s[i] 仍然不相等，所以这条语句不能是 if 而应该是 while；同时我们不能允许j无限制的回退，所以 while 循环里加上一条限制 j > 0，如果最后j都等于0了仍然匹配不了 s[j] 和 s[i]，那我们记 next[i] = 0 ，同时放弃匹配当前的后缀尾指针所指字符 s[i] 。

3. 处理两指针所指字符相等情况

在这种情况下我们对 s[j] 和 s[i] 内容进行比较，发现两者相同，那么前缀尾指针j就要向后移一位；

同时不要忘了将新的next数组值 j 存储到next数组的后缀尾指针所指位置 next[i] ；

流程走完后回到for循环，后缀尾指针i将向后移动。

总结

写 getNext() 函数关键就是理解前缀尾指针j的含义，j的值反映了模式串中头字符到当前下标位置的字符（包括当前位置）中最长相等前后缀的长度。

匹配函数strStr()的实现

int strStr(string haystack, string needle) { //haystack文本串，needle模式串
    //初始化：next数组，i为文本串指针，j为模式串指针
    int next[needle.size()];
    getNext(next, needle);
    int j = 0;
    for (int i = 0; i < haystack.size(); ++i) {
        //处理两指针所指字符不同情况
        while (j > 0 && haystack[i] != needle[j]) {
            j = next[j - 1];
        }
        //处理两指针所指字符相同情况
        if (haystack[i] == needle[j]) ++j;
        if (j == needle.size()) return (i - needle.size() + 1);
    }
    return -1;
}

1. 初始化

使用getNext()函数取得next数组；使文本串指针i初始化到文本串头部，模式串指针j初始化到模式串头部；使用for循环遍历文本串。

2. 处理两指针所指字符不等情况

观察下这部分的代码可以发现跟 getNext() 第二部分是及其相似的，不同的地方只有while循环的判断条件更改了。

当文本串指针i所指字符与模式串指针j所指字符不等时，需要查找 next[j - 1] 的值来回溯模式串指针j，直到回溯到下标为0的位置或发现匹配的字符。

3. 处理两指针所指字符相等情况

如果两指针所指字符相等那么很简单，文本串指针i（隐藏在for循环的 ++i 中）和模式串指针j都自增一次。

如果模式串的最后一个字符被匹配，那么j将等于模式串的长度（注意字符串下标是从0开始），这时通过公式 i - needle.size() + 1 可以得到文本串与模式串匹配的第一个下标。

如果直到for循环结束（遍历完整个文本串）都没能找到完全匹配模式串的子串，那么直接 return -1 表示未找到匹配的子串。

完整代码

class Solution {
public:
    int strStr(string haystack, string needle) { //haystack文本串，needle模式串
        //初始化：next数组，i为文本串指针，j为模式串指针
        int next[needle.size()];
        getNext(next, needle);
        int j = 0;
        for (int i = 0; i < haystack.size(); ++i) {
            //处理两指针所指字符不同情况
            while (j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j]) ++j;
            if (j == needle.size()) return (i - needle.size() + 1);
            //处理两指针所指字符相同情况
        }
        return -1;
    }

    void getNext(int* next, const string& s) {
        //初始化：next[0] = 0，j为前缀尾指针，i为后缀尾指针
        next[0] = 0;
        int j = 0;
        for (int i = 1; i < s.size(); ++i) {
            //处理两指针所指字符不同情况
            while (j > 0 && s[j] != s[i]) {
                j = next[j - 1];
            }
            //处理两指针所指字符相同情况
            if (s[j] == s[i]) ++j;
            next[i] = j;
        }
    }
};

总结

这篇文章从理论和代码两方面介绍了KMP算法。

理论篇以问题环环相扣的方式，试着让理解KMP算法有一个清晰的顺序，并采用了一种明晰的next数组定义方式——直接取为前缀表，方便理解和记忆。

代码篇总结了 strSte() 和 getNext() 两个函数的共同点，给出了KMP代码的一般套路，在理解的基础上记忆能够很快地手撕出KMP。

写这篇不到7k字的文章用了整整一天，有些过于耗时了。不过我本人在写这篇文章的过程中的确收获颇丰，对KMP算法有了更深层次地理解，同时也锻炼了文字表达能力，在Leetcode上第四次手撕KMP也成功在5分钟内一次AC，共勉！

Leetcode

#Leetcode #算法 #KMP #C++

Sunshine + Moonlight 实现低延迟远程串流上一篇

Leetcode59.螺旋矩阵 II 下一篇