“Always bear in mind that your own resolution to succeed is more important than any other.”
前言
KMP算法一直是字符串匹配中经常提到的算法,它能避免不必要的字符比较从而减少字符串匹配所需的时间。其中KMP的全称是Knuth-Morris-Pratt,从 维基百科 可知,该算法由 Donald Knuth,James H. Morris 以及 Vaughan Pratt 同时提出。
The algorithm was conceived in 1970 by Donald Knuth and Vaughan Pratt, and independently by James H. Morris. 1
很早以前我就想对KMP算法的原理以及实现做一个总结,但由于教材上晦涩难懂的介绍以及自身的拖延症属性,这项工作一直拖到了现在。在一个百无聊赖的下午,我看到了 jakeboxer 关于KMP算法的博客2,博客里关于部分匹配表的介绍完美地解释了KMP算法的原理,在此基础上,我将使用自己的语言介绍一下KMP算法具体的代码实现以及可优化空间。
KMP算法
简单字符串匹配算法
在介绍KMP算法前,我想介绍一种原始的字符串匹配算法——简单字符串匹配算法。当我们在串 S 中找串 P 时,串 S 被称为主串,串 P 被称为子串。简单字符串匹配算法可以总结为一句话:在一趟从主串的某一下标开始的字符比较中,如果出现主串和子串对应的字符不匹配,那么主串的下标将前移一位,子串下标回到开头,并开始一趟新的比较。这样说来可能晦涩难懂,下面将通过一个例子演示这个过程,假设主串为 “babaabd”,子串为 “abad”:
初始过程
1
2
3
4
// x 代表不匹配
b a b a a b d
x
a b a d
‘b’ 和 ‘a’ 不相同,开始下一趟匹配
1
2
3
b a b a a b d
|
a b a d
主串和子串对应字符相同,此趟匹配继续
1
2
3
4
5
6
7
8
9
10
11
12
// x 代表不匹配
b a b a a b d
| |
a b a d
b a b a a b d
| | |
a b a d
b a b a a b d
| | | x
a b a d
‘a’ 和 ‘d’ 不相同,开始下一趟匹配
1
2
3
4
// x 代表不匹配
b a b a a b d
x
a b a d
‘b’ 和 ‘a’ 不相同,开始下一趟匹配
1
2
3
b a b a a b d
|
a b a d
主串和子串对应字符相同,此趟匹配继续
1
2
3
4
// x 代表不匹配
b a b a a b d
| x
a b a d
‘a’ 和 ‘b’ 不相同,到达主串末端,字符串匹配结束
简单字符串匹配算法的时间复杂度为 O(m*n),同时该算法符合常理、简单易懂。但是,该算法存在一些问题,在上图的某一趟匹配中(如下列出),此时 ‘a’ != ‘d’,所以应当开始下一趟匹配,如下图的 next 所示。但 KMP 算法有所不同,在KMP算法的下一趟匹配中,子串直接”前移”了两个字符,从而避免了某些不必要的字符比较。KMP 算法之所以能够实现这种”跳跃”,得益于部分匹配表的支持,下一小节将着重介绍部分匹配表。
1
2
3
4
5
6
7
8
9
10
11
12
13
// x 代表不匹配
// 'a'!= b
b a b a a b d
| | | x
a b a d
// next
b a b a a b d
x
a b a d
// KMP algorithm's next
b a b a a b d
|
a b a d
部分匹配表
在介绍部分匹配表前,我想介绍一下字符串的「前缀」和「后缀」。
Prefix and suffix are special cases of substring. A prefix of a string S is a substring of S that occurs at the beginning of S. A suffix of a string S is a substring that occurs at the end of S.
从上可知,前缀(prefix)指的是包含字符串第一个字符的所有连续子串(不包括该字符串),后缀(suffix)指的是包含字符串最后一个字符的所有连续子串(不包括该字符串)。
这么说可能有些复杂,举个例子,假设字符串 S = “abababca”,S 的所有「前缀」和「后缀」如下所示:
1
2
3
4
5
6
7
8
// 前缀 //后缀
a a
ab ca
aba bca
abab abca
ababa babca
ababab ababca
abababc bababca
KMP 算法的关键在于部分匹配表,部分匹配表中每个下标的值(value)代表当前已匹配的字符串的相同前后缀的最大长度,这样说来有点拗口,我们将这个概念拆分开来:
-
当前已匹配的字符串指的是主串和子串已经匹配的部分,下图中 “aba” 就是当前已匹配的字符串。
1 2 3
b a b a a b d //主串 | | | a b a d //子串
-
相同前后缀指的是该字符串 “aba” 前缀和后缀相同的情况,而最大长度指的是前后缀相同的情况下其长度的最大值。如下将列出该字符串的所有前缀和后缀:
1 2 3
//前缀 //后缀 a a //前后缀相同 ab ba //前后缀不同
上述情况下,相同前后缀的最大长度就是 1。
我们将字符串 S: “abababca” 作为「字符串匹配」的子串,如下将给出子串 S 的部分匹配表 :
1
2
3
char: a b a b a b c a
index: 0 1 2 3 4 5 6 7
value: 0 0 1 2 3 4 0 1
index代表「当前已匹配的字符串」,value代表「相同前后缀的最大长度」,我们取出几种情况进行举例分析,其余情况以此类推。
1
2
// index = 0 -> string = "a"
字符串 "a" 无前缀和后缀,value = 0
1
2
3
4
// index = 1 -> string = "ab"
//前缀 //后缀
a b
前后缀不相同,value = 0
1
2
3
4
5
6
7
8
// index = 5 -> string = "ababab"
//前缀 //后缀
a b
ab ab
aba bab
abab abab
ababa babab
其中 "abab" 为最长相同前后缀,因此 value = 4
原理介绍
了解部分匹配表后,KMP 算法可以理解为一句话:每当碰到主串和子串字符不匹配时,子串往前移动的步数为「当前已匹配字符串的长度 - 已匹配字符串在部分匹配表中的 value」。
这句话读起来很拗口,我们将使用通俗的语言从两个方面介绍这句话:
含义
在简单字符串匹配算法中,碰到主串和子串字符不匹配时,子串应该往前移动一步,如下所示:
1
2
3
4
5
6
7
8
9
// x 代表不匹配
// 不匹配('c' != 'd')
a b c d e f
| | x
a b d c
// 子串前移一步
a b c d e f
x
a b d c
而在 KMP 算法中,这个移动的步数不是 1,而是由「当前已匹配字符串」的长度和其在「部分匹配表」中的 value 共同决定。由于在上文中我们已经得出了字符串 “abababca” 的部分匹配表,我们将其作为子串,另外,我们假设主串为 “bacbababaabcbab”,下文将阐述使用 KMP 算法进行字符串匹配的详细过程。
初始时刻
1
2
3
4
// x 代表不匹配
b a c b a b a b a a b c b a b
x
a b a b a b c a
‘b’ != ‘a’,不存在已匹配的字符串,因此子串前移 1 步(与简单字符串匹配算法相同)
1
2
3
4
// x 代表不匹配
b a c b a b a b a a b c b a b
| x
a b a b a b c a
‘c’ != ‘b’,已匹配的字符串为 “a”,查表可知 value = 0,因此子串前移 len(“a”) - 0 = 1 步
1
2
3
4
// x 代表不匹配
b a c b a b a b a a b c b a b
x
a b a b a b c a
‘c’ != ‘a’,前移一步(同「简单字符串匹配算法」)
1
2
3
4
// x 代表不匹配
b a c b a b a b a a b c b a b
x
a b a b a b c a
‘b’ != ‘a’,前移一步(同「简单字符串匹配算法」)
1
2
3
4
// x 代表不匹配
b a c b a b a b a a b c b a b
| | | | | x
a b a b a b c a
‘a’ != ‘b’,已匹配的字符串为 “ababa”,查表可知 value = 3,因此子串前移 len(“ababa”) - value = 5 - 3 = 2 步
1
2
3
4
// x 代表不匹配
b a c b a b a b a a b c b a b
| | | x
a b a b a b c a
‘a’ != ‘b’,已匹配的字符串为 “aba”,查表可知 value = 1,因此子串前移 len(“aba”) - value = 2 步
1
2
3
b a c b a b a b a a b c b a b
|
a b a b a b c a
移动 1 步后已经到达主串末端,匹配结束
上述就是 KMP 算法的通俗理解过程,至于为什么这么做是可行的,以及部分匹配表如何构造等内容我们放在下一部分讲解。相信通过上述过程,你应该能够理解 KMP 算法的大致原理以及工作过程。
为什么这样可行?
这一小节介绍为什么这样跳过是可行的,我们将从两个方面解释这种做法的正确性。
-
因为我们找到了「前缀和后缀相同」的情况,因此当我们将子串前移相应的步数后,子串和主串已经匹配的字符和移动前一致(下图中的 “aba”),因此我们只需要从下一个字符(主串的 “a” 和子串的 “b”)开始进行比较即可。
1 2 3 4 5 6 7 8 9 10 11 12
//移动前(x代表不匹配,o代表跳过的位置),已经匹配的字符为 "aba" b a c b a b a b a a b c b a b | | | | | x a b a b a b c a //'a' != 'b',移动 len("ababa") - 相同前后缀的最大长度 = 2 步 //最长的相同前后缀为"aba",可以发现跳过相应的步数后,子串的"aba" //和主串的"aba"是匹配成功的状态(这一点得益于相同的前缀和后缀) //我们只需要考虑主串和子串接下来的字符即可(主串的 'a' 与子串的 'b') b a c b a b a b a a b c b a b o | | | x a b a b a b c a
-
因为「部分匹配表」存放的是已匹配字符串的相同前后缀的最大长度,因此跳过(上图中用o表示)的位置不存在子串和主串匹配成功的情况。
可以用反证法证明,如果跳过的位置存在主串和子串能够成功匹配的情况,那么「部分匹配表」对应的值肯定不是当前的值(比现在这个值更大)。
举个例子,下图中,已经匹配成功的字符串为 “ababa”,相同前后缀的最大长度为3(前缀 “aba” = 后缀 “aba”),我们应该前移 5 - 3 = 2 步。我们发现,在匹配时跳过了主串的 ‘b’,因为我们能够确认从主串的 ‘b’ 开始的这趟匹配最后肯定会失败,如果不失败的话,以 ‘b’ 开头的这个后缀一定和其对应长度的前缀相同,因此,相同前后缀的最大长度肯定不会是 3,而是 4。
所以我们可以保证,跳过的情况不会包含「匹配成功」,这样保证了该方法的正确性。
1 2 3 4 5 6 7 8
// x means mismatch, o means skip a b a b a b a c d | | | | | x a b a b a c // after moving a b a b a b a c d o | | | | | | a b a b a c
代码实现
KMP 算法的关键在于如何实现两个内容:「借助部分匹配表跳过不必要的匹配」以及「如何生成部分匹配表」
跳过不必要的匹配
前文中我们提到了「子串往前移动 x 步」这个概念,该概念是为了帮助我们理解 KMP 算法的原理。在实际的匹配过程中主串 S 和子串 P(也称模式串)各自拥有一个下标 i,j。每当碰到对应字符不匹配时(称为失配点),调用函数 f(x) 将子串 P 的下标 j 设置为 f(x)。函数 f(x) 实际上就是上文提到的「部分匹配表」(很多情况下也被称为「失败函数」),而参数 x 指的是「当前已匹配字符串的长度」,我们将以代码的角度从头阐述一遍 KMP 算法的具体实现过程
子串 “abababca” 的部分匹配表 f( x ) 如下所示:
1
2
3
char: a b a b a b c a
x: 0 1 2 3 4 5 6 7
f(x): -1 0 0 1 2 3 4 0
需要注意以下几点:
-
在该例子中,主串 S = “bacbababaabcbab”,子串 P = “abababca”。
-
该「部分匹配表」其实跟上述「部分匹配表」内容一致,只是 index 和 x 的值代表的含义有一些细微差异,上述「部分匹配表」中的 index 表示该下标对应的字符串,如 index = 0,表示已匹配字符串为 “a”,index = 1,表示已匹配字符串为 “ab”。而 x 表示已匹配字符串的长度,如 x = 0,表示没有已匹配的字符串,x = 1,表示已匹配的字符串为 “a”,简单地说,x = index - 1,表示所有的值都向右移了一位。除此之外,两个部分匹配表在本质上没有区别。
-
当主串 S 和 子串 P 对应的字符相等时,两者的下标均加一,即 i++,j++。
-
此处的 x 代表已经匹配的字符串长度,当 x = 0 时,代表已匹配的字符串长度为空,我们将部分匹配表的值设置为 特殊值 -1,这种情况下主串 S 和子串 P 的当前下标 i 和 j 都要加1,即下图所代表的情况:
1 2 3 4
// x 代表不匹配 S: b a c b a b a b a a b c b a b // i = 0 x P: a b a b a b c a // j = 0
通过查表发现 f(x) = -1,表示 i++ 且 j++
1 2 3
S: b a c b a b a b a a b c b a b // i = 0 + 1 = 1 | P: a b a b a b c a // j = -1 + 1 = 0
当 x > 0 时,则代表相应的已匹配字符串。如 x = 1,已匹配的字符串为 “a”,x = 2,已匹配的字符串为 “ab”。而 f(x) 则代表子串 P 的当前下标 j 应该设置的值,讨论下述情况:
1 2 3 4
// x 代表不匹配 S: b a c b a b a b a a b c b a b // i = 9 | | | | | x P: a b a b a b c a // j = 5
上图中已匹配的字符串为 “ababa”,代表 x = 5,通过查表可知 f(x) = 3,即 j =3, i 不变,如下图所示:
1 2 3 4 5
// 下一步待比较的是主串 S 的 'a' 以及子串 P 的'b' // o 代表"跳过" S: b a c b a b a b a a b c b a b // i = 9 o | | | x P: a b a b a b c a // j = 3
仔细观察,是不是发现这种处理方法和我们之前介绍的「子串向前移动 2 步(已匹配的字符串长度 - 对应部分匹配表的值 value )」在本质上是一样的呢?只不过是换了种说法而已。除此之外,子串向前移动 2 步这种解释比上述包含 i 和 j 的解释更加通俗易懂。
这样我们通过两个下标 i 和 j,就描述了在某一趟匹配中,如果出现对应字符不匹配,KMP 算法是如何通过「部分匹配表」跳过某些不必要的匹配的。
如何生成部分匹配表?
上一小节中,我们介绍了如何利用「部分匹配表」进行不必要匹配的跳跃,这一小节我们将阐述如何生成「部分匹配表」。在此之前我们可以先进行 KMP 算法主体代码的书写,如下所示,其中 f(x) 就是我们提了很多遍的「部分匹配表」:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// f 表示部分匹配表,假设此处已经生成
// s 为主串,p 为子串
int String::FindKMP(String &s,String &p){
int i = 0; //主串当前下标
int j = 0; // 子串当前下标
int slen = s.n; //主串长度
int plen = p.n; //子串长度
while(i<slen&&j<plen){
if(j==-1||s[i]==p[i]){
i++;
j++;
}else{
j = f[j];// j从0开始,此时j刚好代表已匹配字符串的长度
}
}
return (j==plen) ? (i-plen) : -1;
}
主体代码如上所示,这与上一小节描述的内容一致。接下来,我们将着重分析「部分匹配表」的生成。
「部分匹配表」的生成是在子串 P 上做文章,我先阐述一下常规的做法,如下所示:
已知 f(0) = -1,f(1) = 0,所以我们从「已匹配的字符串」”ab” 开始,即计算 f(2)
初始状态如下所示,因为前缀不需要最后一个字符,后缀不需要第一个字符
我们需要一个变量 k,用于统计当前有多少连续的相等的字符
1
2
3
a b a b a b c a //后缀
|
a b a b a b c a //前缀
‘b’ != ‘a’,且 k = 0,所以 f(2) = 0,前缀所在的字符串应当右移一位,开始找 f(3)
1
2
3
a b a b a b c a //后缀
|
a b a b a b c a //前缀
‘a’ == ‘a’,且 k = 1,所以 f(3) = 1,开始找 f(4)
1
2
3
a b a b a b c a //后缀
| |
a b a b a b c a //前缀
‘b’ == ‘b’,且 k = 2,所以 f(4) = 2,开始找 f(5)
1
2
3
a b a b a b c a //后缀
| | |
a b a b a b c a //前缀
‘a’ == ‘a’,且 k = 3,所以 f(5) = 3,开始找 f(6)
1
2
3
a b a b a b c a //后缀
| | | |
a b a b a b c a //前缀
‘b’ == ‘b’,且 k = 4,所以 f(6) = 4,开始找 f(7)
1
2
3
4
// x 代表不匹配
a b a b a b c a //后缀
| | | | x
a b a b a b c a //前缀
‘c’ != ‘a’,且 k 变为 0,此时下面那个字符串(前缀所在的字符串应当右移一位)
1
2
3
4
// x 代表不匹配
a b a b a b c a //后缀
x
a b a b a b c a //前缀
‘b’ != ‘a’,继续右移
1
2
3
a b a b a b c a //后缀
|
a b a b a b c a //前缀
‘a’ == ‘a’,且 k = 1,此时还没到 f(7) 对应的字符串 “abababc”,继续看两者的下一个字符
1
2
3
a b a b a b c a //后缀
| |
a b a b a b c a //前缀
‘b’ == ‘b’,且 k = 2,此时还没到 f(7) 对应的字符串 “abababc”,继续看两者的下一个字符
1
2
3
4
// x 代表不匹配
a b a b a b c a //后缀
| | x
a b a b a b c a //前缀
‘c’ != ‘a’,且 k 变为 0,前缀所在的字符串右移一位
1
2
3
4
// x 代表不匹配
a b a b a b c a //后缀
x
a b a b a b c a //前缀
‘b’ != ‘a’,继续右移
1
2
3
4
// x 代表不匹配
a b a b a b c a //后缀
x
a b a b a b c a //前缀
‘c’ != ‘a’,且已经到达 f(7) 对应的字符串,此时 k = 0,所以 f(7) = 0,前缀所在的字符串右移一位,找 f(8)
1
2
3
a b a b a b c a //后缀
|
a b a b a b c a //前缀
‘a’ == ‘a’,且 k = 1,所以 f(8) = 1,「部分匹配表」构造结束
不知道聪明的小伙伴有没有发现一些端倪,一样的字符串匹配!一样的”碰到字符不匹配后某个字符串右移”!这不就是一个字符串匹配问题吗?我们在用上述方法做的时候是不是也考虑了一些不必要的情况呢?
虽然你可能很不情愿,但我们确实做了一些无用功,把上述的某一个步骤拿出来看看:
1
2
3
4
// x 代表不匹配
a b a b a b c a //后缀
| | | | x
a b a b a b c a //前缀
这是我们在找 f(7) 即 “abababc” 的「相同前后缀的最大长度」时,碰到了 ‘c’ != ‘a’ 的情况,我们原本的做法是在下一步时使下面那个字符串右移一位,如下所示:
1
2
3
4
// x 代表不匹配
a b a b a b c a //后缀
x
a b a b a b c a //前缀
仔细看看上面那个步骤,”abab” 已经匹配,并且 f(4) 已经被计算出来,为 2,即字符串 “abab” 最长相等的前缀和后缀为 “ab”,长度为 2。因此,我们在右移「前缀所在的字符串」时是不是也可以像 KMP 算法那样移动 len(已匹配的字符串) -「部分匹配表」对应的值 = len(“abab”) - value = 4 - 2 = 2 呢? 如下图所示:
1
2
3
4
// o 代表跳过
a b a b a b c a //后缀
o o | | x
a b a b a b c a //前缀
我们可以为前缀和后缀所在的字符串分别声明一个下标 j 和 k,跟 KMP 算法类似地,每当遇到字符不匹配时,我们通过已经生成的「部分匹配表」更新 k 的值并进行下一趟匹配,详细的代码如下所示:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void String::f(String &p){
int j = 0;
int k = -1;
int len = p.n;//子串 p 的长度
f[0] = -1;
while(j<n){
if(k==-1||(str[j]==str[k])){
k++;
j++;
f[j] = k;
}else{
k = f[k];
}
}
}
怎么样?是不是和 KMP 算法很像?说起来这也是一件有趣的事,我们要计算「部分匹配表」,在计算的过程中我们却用到了「部分匹配表」,我们因为要实现 KMP 算法转而去计算「部分匹配表」,在计算「部分匹配表」的过程中我们却用到了 KMP 算法的思想。
代码优化3
这样其实已经比较快了,但是 KMP 算法在构造「部分匹配表」其实还可以优化,考虑到如下情况(主串为 “abcadddd”,子串为 “abcab”):
1
2
3
a b c a d d d d //主串 i = 4
| | | | x
a b c a b //子串 j = 4
此时调用 f(4) = 1,则令 j = 1,如下所示:
1
2
3
a b c a d d d d //主串 i = 4
| x
a b c a b //子串 j = 1
此时调用 f(1) = 0,则令 j = 0,如下所示:
1
2
3
a b c a d d d d //主串 i = 4
x
a b c a b //子串 j = 0
我们可以发现,对于子串 “abcab”,因为前缀 “ab” = 后缀 “ab”,因为在调用 f(4) 之前,主串的 ‘d’ != 子串的 ‘b’ (位于尾巴处),又因为调用 f(4) 之后,子串的下一个字符也是 ‘b’ (位于开头处) 肯定不等于主串的 ‘d’,因此可以直接调用 f(1) 而不用调用 f(4)。
我们可以在生成「部分匹配表」时规避这种情况,还是以上述子串 “abcab”生成「部分匹配表」的过程为例,当我们计算 f(4) 时,如下所示:
1
2
3
a b c a b // j = 3
|
a b c a // k = 1,代表已匹配的字符串长度为 1
我们知道 f(4) = 1,但是当我们比较一下发现下一个字符(j++, k++) ‘b’ == ‘b’,如下所示:
1
2
3
a b c a b // j = 4
| |
a b c a // k = 2
又因为在如下场景中,后缀没法匹配上( ‘d’ != ‘b’ ),因为前缀这部分和后缀相同( “ab” ),所以经过一次右移后,还是无法匹配上,所以干脆不如直接调用 f(1)( 为什么是 f(1),因为 1 是计算 f(4) 前已经匹配的字符串长度 ),跳过调用 f(4) 的这趟匹配:
1
2
3
4
5
6
7
8
// x代表不匹配
a b c a d d d d //主串 i = 4
| | | | x
a b c a b //子串 j = 4 ('d' != 'b')
// 子串右移后,肯定还会出现 'd' != 'b' 的情况
a b c a d d d d //主串 i = 4
| x
a b c a b //子串 j = 1
因此我们在生成「部分匹配表」时进行判断,两个字符串的下一个字符是否相等,如果不相等,则将累计变量 k (已匹配的连续字符数) 放入部分匹配表中,如果相等则将该值设为 f(k),具体代码如下所示:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void String::f(String &p){
int j = 0;
int k = -1;
int len = p.n;//子串 p 的长度
f[0] = -1;
while(j<n){
if(k==-1||(str[j]==str[k])){
k++;
j++;
if(str[j]==str[k]){
f[j] = f[k];
}else{
f[j] = k;
}
}else{
k = f[k];
}
}
}
后记
其实很早以前就想写 KMP 算法的博客了,一直拖到现在。希望我的博客能够帮助你更好地理解 KMP 算法,也希望自己在写完这篇博客后能够认真对待碰到的每个问题,研究生生涯能够有所收获。
—— 2019.07.16 23:00