目录

字符串匹配——KMP算法详解

前言

字符串的匹配在任何系统中都是最流行的功能,许多算法可以完成这个任务,KMP是最常用的算法之一。它的名字跟功能并没有任何关联,仅仅是以三个发明者姓名首字母的缩写(Knuth-Morris-Pratt),起头的那个K就是著名科学家Donald Knuth。KMP是我刷算法遇到的第一块难啃的骨头,这完全不是能不能想到的问题,而是完全看不懂,学到最后不得不佩服发明者的脑洞之大。网络上已有很多能够详细分析该算法的文章,但我一直看的还是云里雾里,最终决定花些时间写一个更加通俗易懂的版本(至少对我是如此),其中些许可能与众不同的地方大多已做说明,希望能对大家有所启发。

基本定义1

字符串

字符串S是将n个字符顺次排列形成的序列,其中n称为S的长度,S的第i个字符表示为S[i]。(在有的地方,也会用S[i-1]表示第i个字符。)

子串

字符串S的子串S[i:j],(i<j)表示S串中从ij这一段顺次排列的字符串。

后缀

后缀:指从某个位置i开始到整个串末尾结束的一个特殊子串。字符串Si开头的后缀表示为Suffix(S,i)

真后缀:指除了S本身的其它后缀。

示例:字符串abcabcd的所有后缀为{d, cd, bcd, abcd, cabcd, bcabcd, abcabcd},而它的真后缀为{d, cd, bcd, abcd, cabcd, bcabcd}

前缀

前缀:指从串首开始到某个位置i结束的一个特殊子串。字符串Si结束的前缀表示为Prefix(S,i)

真前缀:指除了S本身的其它前缀。

示例:字符串abcabcd的所有前缀为{a, ab, abc, abca, abcab, abcabc, abcabcd},而它的真前缀为{a, ab, abc, abca, abcab, abcabc}

KMP算法

假设需要匹配的主串为:txt="BBC ABCDAB ABCDABCDABDE",匹配的模式串为:pat="ABCDABD",下标索引从0开始。

https://cdn.jsdelivr.net/gh/wefantasy/FileCloud/img/202203220953203.png
示例

常规字符串匹配算法

很容易想到的是暴力匹配算法,我们从主串txt的第一个字符开始检查其是否与模式串pat的第一个字符匹配2

https://cdn.jsdelivr.net/gh/wefantasy/FileCloud/img/202203221007374.gif
暴力匹配算法

  1. 首先,主串BBC ABCDAB ABCDABCDABDE的第1个字符B与模式串ABCDABD的第1个字符A进行比较。因为BA不匹配,所以模式串后移1位。
  2. 然后,尝试匹配主串的第2个字符与模式串的第1个字符,匹配失败,模式串继续后移。
  3. ……。就这样,直到与模式串的第一个字符相同为止,本例中为txt的第4个字符A
  4. 匹配成功后依次匹配主串和模式串的下一个字符,直到模式串匹配完成或者中途匹配失败。
  5. ……。就这样,直到匹配到主串第11个字符 时,与模式串匹配失败。
  6. 然后,将模式串后移1位,重新开始以上流程循环匹配。
    一个简单的伪代码实现如下:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func search(txt string, pat string) int {
	m, n := len(pat), len(txt)
	for i := 0; i < n-m; i++ {
		j := 0
		for ; j < m; j++ {
			if pat[j] != txt[i+j] {
				break
			}
		}
		if j == m {
			return i
		}
	}
	return -1
}

在暴力算法中,如果出现不匹配字符,同时回退txtpat的指针,嵌套for循环,时间复杂度$O(MN)$,空间复杂度$O(1)$。

最长公共前后缀

暴力算法效率低的根本原因是每次匹配失败都会完全回退pat指针,以致进行了大量重复的匹配,因此根据动态规划的思想3我们可以设置一个数组存放匹配记录,在每次回溯模式串指针时根据数组调整回溯的位置(而非回到起点),以空间换时间的方式提高算法效率,这样的一个数组就是最长公共前后缀数组Comfix数组),也称next数组、部分匹配表、前缀表。那什么是最长公共前后缀呢?

给定一个长度为n的字符串S,其最长公共前后缀被定义为一个长度为n的数组Comfix。其中Comfix[i]的定义是:

  1. 如果子串S[0:i]有一对相等的真前缀与真后缀:S[0:k-1]==S[i-(k-1):i],那么Comfix[i]就是这个相等的真前缀(真后缀)的长度,也就是Comfix[i]=k
  2. 如果不止有一对真前缀与真后缀相等,那么Comfix[i]就是其中最长的那一对的长度。
  3. 如果没有相等的,那么Comfix[i]=0,特别的Comfix[0]=0

对于本例的pat模式串ABCDABD来说:

https://cdn.jsdelivr.net/gh/wefantasy/FileCloud/img/202203221038885.png
最长公共前后缀

  • Comfix[0]=0,因为A的前缀和后缀都为空集,共有元素的长度为0。
  • Comfix[1]=0,因为AB的前缀为[A],后缀为[B],共有元素的长度为0。
  • Comfix[2]=0ABC的前缀为[A,AB],后缀为[BC,C],共有元素的长度0。
  • Comfix[3]=0ABCD的前缀为[A,AB,ABC],后缀为[BCD,CD,D],共有元素的长度为0。
  • Comfix[4]=1ABCDA的前缀为[A,AB,ABC,ABCD],后缀为[BCDA,CDA,DA,A],共有元素为A,长度为1。
  • Comfix[5]=1ABCDAB的前缀为[A,AB,ABC,ABCD,ABCDA],后缀为[BCDAB,CDAB,DAB,AB,B],共有元素为AB,长度为2。
  • Comfix[6]=1ABCDABD的前缀为[A,AB,ABC,ABCD,ABCDA,ABCDAB],后缀为[BCDABD,CDABD,DABD,ABD,BD,D],共有元素的长度为0。

最长公共前后缀应用

在暴力算法中,当我们遇到不匹配时,会直接将模式串后移一位并从头匹配:

https://cdn.jsdelivr.net/gh/wefantasy/FileCloud/img/202203221048534.gif
暴力算法从头匹配

在引入最长公共前后缀后,我们发现,当遇到不匹配时完全可以将与模式串已匹配的(最长)真后缀相等的真前缀直接移到真后缀这里

https://cdn.jsdelivr.net/gh/wefantasy/FileCloud/img/202203221103365.gif
最长公共前后缀匹配

在上图中,我们匹配到索引10的字符时发现不匹配,查看已匹配的模式串ABCDAB中有一个长度为2的最长公共前后缀AB,于是直接将公共前缀的AB移到公共后缀的AB位置处4,然后在继续从索引处10开始匹配。将过程从数学上来表示就是,每次发现不匹配时,就将模式串向右移动 已匹配的模式串长度-已匹配的模式串最长公共前后缀长度 个单位。

代码实现

计算最长公共前后缀数组

KMP算法最难理解的部分就是最长公共前后缀数组Comfix的计算,现以模式串ABCDABD为例说明详细计算过程:

https://cdn.jsdelivr.net/gh/wefantasy/FileCloud/img/202203221228246.gif
最长公共前后缀数组计算

  1. 初始化Comfix[0]=0j=0,从索引i=1开始遍历模式串。
  2. i=1,2,3时,j=0pat[i]!=pat[j],所以Comfix[1,2,3]=j=0
  3. i=4时,j=0pat[i]==pat[j],先使j=j+1,所以Comfix[4]=j=1
  4. i=5时,j=1pat[i]==pat[j],先使j=j+1,所以Comfix[5]=j=2
  5. i=6时,j=2pat[i]!=pat[j],需要回溯:
    • 使j=j-1,此时i=6j=1pat[i]!=pat[j]
    • 使j=j-1,此时i=6j=0pat[i]!=pat[j]Comfix[6]=j=0

注意:

  1. 这里应当明白,Comfix数组中的每个元素的值都与上一个元素的值相关,且Comfix[i+1]最多只比Comfix[i]大1;
  2. j始终指向最长前缀的末端,所以j本身亦可代表所指向最长前缀的长度。
  3. 网上很多实现中Comfix数组是Comfix[0]=-1,与本例中区别只是边界判断方法不同,并无优劣。

上述流程的Golang实现代码为5

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func getComfix(s string) []int {
	n := len(s)
	comfix := make([]int, n)
	comfix[0] = 0
	j := 0
	for i := 1; i < len(s); i++ {
		for j > 0 && s[i] != s[j] {
			j = comfix[j-1]
		}
		if s[i] == s[j] {
			j++
		}
		comfix[i] = j
	}
	return comfix
}

字符串查找代码实现

具体的字符串查找方式就是调用Comfix数组进行匹配,其过程与上文的最长公共前后缀应用描述一致,其大致流程如下:

https://cdn.jsdelivr.net/gh/wefantasy/FileCloud/img/202203221348342.gif
字符串查找过程
与暴力算法相比,KMP算法的复杂度$O(M+N)$,空间复杂度$O(N)$,其匹配部分代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func subStr(txt string, pat string) int {
	n := len(pat)
	if n == 0 {
		return 0
	}
	j := 0
	comfix := getComfix(pat)
	for i := 0; i < len(txt); i++ {
		//匹配失败时j回退至txt[i] == pat[j]或j==0处
		for j > 0 && txt[i] != pat[j] {
			j = comfix[j-1] // 回退到j的前一位
		}
		if txt[i] == pat[j] {
			j++
		}
		if j == n {
			return i - n + 1
		}
	}
	return -1
}

全部Golang测试代码为:

 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
39
40
41
42
43
44
45
46
47
package main

import (
	"fmt"
)

func getComfix(s string) []int {
	n := len(s)
	comfix := make([]int, n)
	comfix[0] = 0
	j := 0
	for i := 1; i < len(s); i++ {
		for j > 0 && s[i] != s[j] {
			j = comfix[j-1]
		}
		if s[i] == s[j] {
			j++
		}
		comfix[i] = j
	}
	return comfix
}
func subStr(txt string, pat string) int {
	n := len(pat)
	if n == 0 {
		return 0
	}
	j := 0
	comfix := getComfix(pat)
	for i := 0; i < len(txt); i++ {
		//匹配失败时j回退至txt[i] == pat[j]或j==0处
		for j > 0 && txt[i] != pat[j] {
			j = comfix[j-1] // 回退到j的前一位
		}
		if txt[i] == pat[j] {
			j++
		}
		if j == n {
			return i - n + 1
		}
	}
	return -1
}

func main() {
	fmt.Println(subStr("BBC ABCDAB ABCDABCDABDE", "ABCDABD"))
}

参考


  1. StudyingFather. 前缀函数与 KMP 算法. OI Wiki. [2021/12/29] ↩︎

  2. 阮一峰. 字符串匹配的KMP算法. 阮一峰的网络日志. [2013-05-01] ↩︎

  3. labuladong. 如何更好地理解和掌握 KMP 算法?. 知乎. [2020-07-15] ↩︎

  4. 天勤率辉. 「天勤公开课」KMP算法易懂版. BiliBili. [2019-04-20] ↩︎

  5. 代码随想录. 实现 strStr(). 代码随想录. [2022-03-09] ↩︎