Knuth-Morris-Pratt (KMP) 算法原理、实现及其优化

"写在研究毫无进展的充电时刻"

Posted by 小兴安岭 on July 4, 2019

“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

参考文献