KMP算法与代码模板

  |  

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

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


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

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

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 的情况:

  1. j = 0,则 ++i。
  2. 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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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 进行标识。满足要求有两点:

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

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

  1. mpnext[j] == 0 && p[j] == p[0]kmpnext[j] = -1
  2. mpnext[j] == 0 && p[j] != p[0]kmpnext[j] = 0
  3. mpnext[j] != 0 && p[j] != p[mpnext[j]]kmpnext[j] = mpnext[j]
  4. 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_nextget_mp_next 的区别仅在给 kmpnext[i+1] 复制之前判断一步 p[i+1]p[j+1]
  • kmp_matchmp_match 完全相同。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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;
}

模板题

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

1
2
3
4
5
6
7
8
9
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 算法

1
2
3
4
5
6
7
8
9
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 扩展1: 利用 mpnext 数组的题目

1
2
3
4
5
6
7
8
9
10
11
12
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;
}
1
2
3
4
5
6
bool repeatedSubstringPattern(string s) 
{
int n = s.size();
vector<int> mpnext = get_mpnext(s);
return mpnext[n] && n % (n - mpnext[n]) == 0;
}
1
2
3
4
5
6
string longestPrefix(string s) {
int n = s.size();
vector<int> mpnext = get_mpnext(s);
int len = mpnext.back();
return s.substr(0, len);
}

Share