KMP算法与代码模板

字数统计: 2.6k字 | 阅读时长: 12分

2023-05-09

leetcode428, 代码模板127, 字符串40, 自动机14, 论文17

摘要: KMP算法原理与代码模板

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章字符串精确匹配中，我们汇总了字符串精确匹配的各种算法，其中 KMP 算法是比较难但是思想比较重要的一种，

本文我们系统串讲一下 KMP 算法，这是一种先预处理再响应查询的思路。KMP 算法预处理出的信息除了字符串精确匹配，还可以解决字符串上的一些其他问题，本文也会给出一些例子。

KMP 算法为 Knuth、Morris、Pratt 在 1977 年提出的算法，论文为《Fast Pattern Matching in Strings》。可以通过下面的链接直接下载。

《Fast Pattern Matching in Strings》

MP 算法

MP 算法，Morris, Pratt 在 1970 提出。与暴力算法相比的改进主要体现在：某次匹配失败时候，i 不回溯，j 往前回溯若干位。

j 往前回溯多少位，有一个函数控制，称为失效函数f：f[j] := 在 [0..j) 范围内，使得 p[0..k] == p[j-k..j] 成立的最大的数 k，若这样的 k 不存在，则取值 -1。其中自变量 j 的含义是失配前已匹配的字符个数，0 <= j <= m - 1。

以模式串 p = caatcat 为例，求 p 的失效函数 f[j]：

j = 0: 0 <= k < 0，k 直接不存在，f 取 -1
j = 1: 0 <= k < 1，k 只能取 1，而 k 取 0 与 p[0] != p[1] 矛盾，因此 f 取 -1
j = 2: k 可取 0, 1, 两个 k 的取值下对应的 p 的条件 p[0]!=p[2]、p[0..1]!=p[1..2]，均矛盾，因此 f 取 -1
j = 3: k 可取 0, 1, 2, p[0]!=p[3], p[0..1]!=p[2..3], p[0..2]!=p[1..3]，均不满足，因此 f 仍然取 -1
j = 4: k 可取 0, 1, 2, 3, p[0]==p[4], p[0..1]!=p[3..4], p[0..2]!=p[2..4], p[0..3]!=p[1..4]，其中 k = 0 时对应的 p[0]==p[4] 满足，因此 f 取 0
j = 5: k 可取 0, 1, 2, 3, 4, p[0]!=p[5], p[0..1]==p[4..5], p[0..2]!=p[3..5], p[0..3]!=p[2..5], p[0..4]!=p[1..5]，k = 1 满足，因此 f 取 1
j = 6: k 可取 0, 1, 2, 3, 4, 5 p[0]!=p[6], p[0..1]!=p[5..6], p[0..2]!=p[4..6], p[0..3]!=p[3..6], p[0..4]!=p[2..6], p[0..5]!=p[1..6]，均满足，因此 f 取 -1

j	0	1	2	3	4	5	6
p[j]	c	a	a	t	c	a	t
f[j]	-1	-1	-1	-1	0	1	-1

因为失效函数 f[j] 仅与模式串 p 有关，与主串 s 无关，因此计算好后，可以用于 s 上匹配的整个过程，通过 f[j] 可以得到与 s 匹配过程中在 p[j] 失配后，j 应回溯到的位置，该位置记为 mpnext[j]。

已经计算好 mpnext[j] 后，匹配的过程与暴力算法相同，仍然是维护 s 和 p 上的双指针 i, j。

在 s 上推进 i, p 上推进 j，当在 p[j] 发生失配 s[i]!=p[j] 时，不回溯 i，看 j 的情况：

j = 0，则 ++i。
j > 0, 则 i 不推进，j 回溯到 f[j-1]+1。

根据以上讨论，以 cattcat 为例，可以将 j, p[j], f[j], mpnext[j]`` 关系整理如下表：

j	0	1	2	3	4	5	6	7
p[j]	c	a	a	t	c	a	t
f[j]	-1	-1	-1	-1	0	1	-1
mpnext[j]	-1	0	0	0	0	1	2	0

其中 mpnext[j] 表示在 p[j] 失配时，j 需要回溯到的位置，在 0 < j < m 时它与 f[j] 的关系是 mpnext[j] = f[j - 1] + 1。j = 0 时需要将 i 推进一位, 记 mpnext[0] = -1。j = 7 即 j = m 的情况是表示已经找到了一个完整匹配。如果 s[i] 之后仍有后续部分，可以继续匹配过程，此时应该将 j 回溯到 0。

时间复杂度 $O(m+n)$

代码 (c++，模板)

按照前面的讨论，整个过程分为两部分: 预处理和匹配，分别为 get_mp_next(p) 和 mp_match(s, p, mpnext)。

int match(string s, string pattern) {
    if(pattern.empty()) 
        return 0;
    vector<int> mpnext = get_mp_next(pattern);
    return mp_match(s, pattern, mpnext);
}

int mp_match(const string& s, const string& p, const vector<int>& mpnext)
{
    int n = s.size(), m = p.size();
    for(int i = 0, j = 0; i < n; ++i)
    {
        while(j > -1 && s[i] != p[j])
            j = mpnext[j];
        ++j;
        if(j == m)
            return i - m + 1;
    }
    return -1;
}

vector<int> get_mp_next(const string& p)
{
    int m = p.size();
    vector<int> mpnext(m + 1, -1);
    for(int i = 0, j = -1; i < m; ++i)
    {
        while(j > -1 && p[i] != p[j])
            j = mpnext[j];
        // j == -1 或 p[i] == p[j]
        ++j;
        mpnext[i + 1] = j;
    }
    return mpnext;
}

KMP 算法

KMP 指的是 Kruth-Morris-Pratt 这三个人，是 1977 年提出的算法。

KMP 与 MP 十分相似，也是分为预处理产生 kmpnext 和利用 kmpnext 匹配这两步。KMP 对 MP 只有一个地方的变化，也是一步优化。

一般也管以上提到的 MP 和 KMP 算法分别称为 KMP 和扩展 KMP 算法。

回顾 MP 的思路

当 p 的左端 p[0] 与 s 的某子串起点 s[i] 对齐，从左向右逐个比较，在 s[i+j] 和 p[j] 处失配。

此时，s[i..i+j-1] 和 p[0..j-1] 是匹配的，见图中蓝色，记为 u。此时 i 保持位置不回溯，往前移动 p ，即回溯 j 然后进行下一轮的逐个比较。

希望移动后的结果可以使得 p 的一个前缀 (记为 v)，可以匹配到 u 的某一部分后缀，见图中粉色。MP 的做法就是找到能够匹配u中某一后缀的最长前缀v。并引入 mpnext[j] 对 p 中符合要求的最长前缀进行标记。

于是 p 向前移动(j = mpnext[j] 回溯j)后，新一轮的比较在 p[mpnext[j]] = c 和 s[i + j] 开始，见图。

KMP 的改进

前移 p 后，下一步是比较 a 和 c，若可以避免 a 和 c 之间的失配，则可以在新一轮匹配前将 p 继续向前推进。但是在预处理生成 mpnext 时，原材料只有 p，而 s 是未知的，因此无法预见 a 和 c 之间的一次失配。

但是在只知道 p 的情况下，可以保证完成一次移动之后，紧随 v 的字符 c 不等于原来失配的字符 b。

KMP 算法使用 kmpnext 对 p 中满足要求的 v 进行标识。满足要求有两点：

v 可以匹配 u 中某个后缀的一个最长前缀 (MP 算法的 mpnext 已经满足这一点)。
紧跟在 v 之后的字符 c 不同于紧跟在 u 之后的字符 b (KMP 对 MP 的优化)。

当已有 mpnext 之后, 建立 kmpnext 的规则，一共有 4 中情况，1 <= j <= m - 1：

mpnext[j] == 0 && p[j] == p[0] 则 kmpnext[j] = -1。
mpnext[j] == 0 && p[j] != p[0] 则 kmpnext[j] = 0。
mpnext[j] != 0 && p[j] != p[mpnext[j]] 则 kmpnext[j] = mpnext[j]。
mpnext[j] != 0 && p[j] == p[mpnext[j]] 则用 mpnext[j] 的值替换原来 mpnext[j] 中的 j 值，直到情况变为前三种之一，进而递归地求 kmpnext[j]。

此外，仍然令 kmpnext[0] = -1, kmpnext[m] = mpnext[m], 目的与 MP 算法相同。

仍以 caatcat 为例，将 kmpnext[j] 的值加入表格中对比：

j	0	1	2	3	4	5	6	7
p[j]	c	a	a	t	c	a	t
f[j]	-1	-1	-1	-1	0	1	-1
mpnext[j]	-1	0	0	0	0	1	2	0
kmpnext[j]	-1	0	0	0	-1	0	2	0

说明：

kmpnext[0] = -1: 规定的值，j 回溯到 0(当前 j 已经是 0)，++i。
kmpnext[j] = -1 (j!=0): p 中，p[j-k..j-1] 与 p[0..k-1] 均不相等，或相等但 p[i]==p[j]。
kmpnext[j] = k (0 < k < j): p 中，p[j-k..j-1] 与 p[0..k-1] 且 p[j] != p[k]。
出以上三种情况，kmpnext[j] = 0。

代码 (C++，模板)

get_kmp_next 与 get_mp_next 的区别仅在给 kmpnext[i+1] 复制之前判断一步 p[i+1] 和 p[j+1]。
kmp_match 与 mp_match 完全相同。

int match(string s, string pattern) {
    if(pattern.empty()) 
        return 0;
    vector<int> kmpnext = get_kmp_next(pattern);
    return kmp_match(s, pattern, kmpnext);
}

int kmp_match(const string& s, const string& p, const vector<int>& kmpnext)
{
    int n = s.size(), m = p.size();
    for(int i = 0, j = 0; i < n; ++i)
    {
        while(j > -1 && s[i] != p[j])
            j = kmpnext[j];
        ++j;
        if(j == m)
            return i - m + 1;
    }
    return -1;
}

vector<int> get_kmp_next(const string& p)
{
    int m = p.size();
    vector<int> kmpnext(m + 1, -1);
    for(int i = 0, j = -1; i < m; ++i)
    {
        while(j > -1 && p[i] != p[j])
            j = kmpnext[j];
        // j == -1 或 p[i] == p[j]
        ++j;
        if(p[i + 1] == p[j])
            kmpnext[i + 1] = kmpnext[j];
        else
            kmpnext[i + 1] = j;
    }
    return kmpnext;
}

模板题

28. 实现 strStr()

给你两个字符串 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 。

提示：

1 2	1 <= haystack.length, needle.length <= 1e4 haystack 和 needle 仅由小写英文字符组成

代码1：MP 算法

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.empty()) 
            return 0;
        vector<int> mpnext = get_mp_next(needle);
        return mp_match(haystack, needle, mpnext);
    }
};

代码2：KMP 算法

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.empty()) 
            return 0;
        vector<int> kmpnext = get_kmp_next(needle);
        return kmp_match(haystack, needle, kmpnext);
    }
};

$3 扩展: 利用 mpnext 数组的题目

mpnext 是 KMP 算法的预处理阶段产生的中间结果。这个预处理出的信息可以解决很多问题，下面是一些例子。

214. 最短回文串利用 s+'#'+s.reverse() 上的 mpnext[n]

string shortestPalindrome(string s) {
    if(s.empty()) return "";
    int m = s.size();
    string t = s + '#' + s;
    reverse(t.begin() + m + 1, t.end());
    vector<int> mpnext = get_mpnext(t);
    int n_add = s.size() - mpnext.back();
    string result = s.substr(m - n_add);
    reverse(result.begin(), result.end());
    result += s;
    return result;
}

459. 重复的子字符串利用 s 的 mpnext[n]。

bool repeatedSubstringPattern(string s) 
{
    int n = s.size();
    vector<int> mpnext = get_mpnext(s);
    return mpnext[n] && n % (n - mpnext[n]) == 0;
}

1392. 最长快乐前缀利用 s 的 mpnext[n]

string longestPrefix(string s) {
    int n = s.size();
    vector<int> mpnext = get_mpnext(s);
    int len = mpnext.back();
    return s.substr(0, len);
}

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法字符串