字符串匹配的KMP算法

字符串匹配是在目标字符串target中查找与字符串pattern相匹配的起始索引位置的算法,字符串匹配算法中,Knuth-Morris-Pratt算法(简称KMP)是比较常用的算法之一。下边通过一个例子来介绍KMP匹配算法。

对暴力匹配的改进

为了引入KMP算法的优势,首先来看低效的暴力匹配方法。现在需要在字符串target中匹配字符串pattern,二者的值如下:

1
2
target  = "ABCABCDABCDABDE";
pattern = "ABCDABD";

使用暴力匹配方法,需要从target的第一个字符开始,依次与pattern匹配:

(注:以下代码段中|表示已匹配且匹配成功,x表示已匹配且匹配失败,?表示即将匹配)

1
2
3
4
#1    012345678901234
tar - ABCABCDABCDABDE
?
pat - ABCDABD

逐个比较字符,直到遇到不同:

1
2
3
4
#2    012345678901234
tar - ABCABCDABCDABDE
|||x
pat - ABCDABD

终止当前的匹配,将target中游标位置右移1,开始新的一轮比较:

1
2
3
4
#3    012345678901234
tar - ABCABCDABCDABDE
?
pat - ABCDABD

由于首个字符不一致,会继续跳过,直到target中首个字符匹配时:

1
2
3
4
#4    012345678901234
tar - ABCABCDABCDABDE
|?
pat - ABCDABD

继续刚才的方法,直到全部匹配成功或出现不一致:

1
2
3
4
#5    012345678901234
tar - ABCABCDABCDABDE
||||||x
pat - ABCDABD

此时,如继续暴力匹配的方法,会进入#6所示的状态:

1
2
3
4
#6    012345678901234
tar - ABCABCDABCDABDE
?
pat - ABCDABD

这是一种极其低效的方法。实际上,在刚才一轮的比较过程中,回到#5所示状态,可以看到参与比较的target中第7-8个字符AB,与pattern的起始部分相匹配,而target的第4-6个字符BCDpattern的起始部分不匹配,这些信息对于计算程序是可知的。如果在进行逐个字符比较的过程中,可以依据这些信息,就能够在开始下次比较时,跳过第4-6个字符,直接将游标移到第7个字符,且从target第9个字符开始比较,即#7所示的状态,则会大大降低比较次数:

1
2
3
4
#7    012345678901234
tar - ABCABCDABCDABDE
||?
pat - ABCDABD

KMP算法即按照这一思路来实现,它会在比较过程中,记录比较信息,进而在下次比较时,跳过target中已经参与过比较的字符,并计算出新的targetpattern中游标的位置,进而大大提高效率。

KMP算法

在KMP算法中,引入局部匹配表(partial match table)的概念,局部匹配表根据匹配字符串pattern生成,是一个长度与pattern相等的整数数组。此处先接着刚才的例子介绍KMP算法的原理,下节介绍局部匹配表如何生成。

对于pattern字符串ABCDABD,局部匹配表T = [-1,0,0,0,0,1,2],即:

1
2
pat :  A B C D A B D
PMT : -1 0 0 0 0 1 2

在每次匹配出现匹配失败时,target中的游标不会回退到上次开始匹配的位置+1处,而是继续向后,并且会根据局部匹配表计算出pattern中游标的位置。

回到刚才#5所示的状态,出现匹配失败时,target中游标索引i=9pattern中游标索引位置k=6

1
2
3
4
5
#5    012345678901234
tar - ABCABCDABCDABDE i = 3 + 6
||||||x
pat - ABCDABD k = 6
0123456

KMP算法使用以下公式计算下次匹配开始时游标的位置(T表示局部匹配表数组),当出现target[i]!=pattern[k]时,下一次的匹配比较将在target[i]和pattern[T[k]]之间进行:

1
2
3
4
5
6
7
8
if(k==0)
{
i++; // 注意:这种情况表示上次匹配中pattern的第一个字符就不匹配
}
else
{
k = T[k];
}

结合本文的例子,对于#5的状态,则会计算出下次匹配时,有i=9以及 k=2,将此状态记为#8

1
2
3
4
5
#8    012345678901234
tar - ABCABCDABCDABDE
?
pat - ABCDABD
0123456

对比发现与之前期望的#7所示状态相同。

使用这种方法对于长度分别为mtarget字符串,计算的时间复杂度为O(m)

初始化局部匹配表

构建局部匹配表的算法,对于长度为n的字符串pattern,时间复杂度为O(n)。使用局部匹配表,可以使target中的字符最多参与一次匹配比较。在字符串pattern内部进行预匹配,查找和记录可能的匹配位置,保存为回退点,用于在出现不匹配时回退,以避免无用的比较。

定义T[0]= -1,除T[0]外后边的T[j]=k的意义可以简单看成是:pattern中下标为j的字符(不含本身)的前面有最多k个字符与pattern起始的k个字符相同。

依然使用之前的例子:

1
pattern = "ABCDABD";

对于pattern对应的局部匹配表,先确定前缀(prefix)和后缀(suffix)的概念,前缀是字符串中从第一个字符开始取到的子字符串,字符串的前缀长度必须小于原字符串。如字符串"HIJKL"有前缀"H""HI""HIJ""HIJK"。后缀的定义与此相似,方向相反。

  1. 首先有T[0] = -1
  2. 接下来确定T[1]的值,比较整个字符串的前缀与pattern[0]的后缀,pattern[0]="A"无后缀,因此有T[1] = 0
  3. 确定T[2]的值,比较整个字符串的前缀与pattern[0-1]的后缀,pattern[0-1]有后缀"B",但与pattern的前缀不一致,因此T[2] = 0
  4. 继续到T[3],比较整个字符串的前缀与pattern[0-2]的后缀,没有匹配的部分,所以T[3] = 0
  5. 继续到T[4],比较整个字符串的前缀与pattern[0-3]的后缀,没有匹配的部分,所以T[4] = 0
  6. 继续到T[5],比较整个字符串的前缀与pattern[0-4]的后缀,pattern[0-4] = "ABCDA",有后缀"A"与整个字符串的前缀"A"相同,相同部分长度为1,因此有T[5] = 1
  7. 最后到T[6],比较整个字符串的前缀与pattern[0-5]的后缀,pattern[0-5] = "ABCDAB",有后缀"AB"与整个字符串的前缀"AB"相同,相同部分长度为2,因此有T[6] = 2
  8. 比较结束,得到T = [-1,0,0,0,0,1,2]

局部匹配表,又称为模式值或模式数组(next[])、失效函数(failure function)等,有若干种相似的定义方式,对应的KMP算法实现也稍有不同。计算局部匹配表的一种方法,及KMP算法的一种c++实现见下节。

KMP算法c++实现

代码来源

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/*
* C++ Program to Implement Knuth–Morris–Pratt Algorithm (KMP)
*/
#include <iostream>
#include <cstring>
using namespace std;
void preKMP(string pattern, int f[])
{
int m = pattern.length(), k;
f[0] = -1;
for (int i = 1; i < m; i++)
{
k = f[i - 1];
while (k >= 0)
{
if (pattern[k] == pattern[i - 1])
break;
else
k = f[k];
}
f[i] = k + 1;
}
}

//check whether target string contains pattern
bool KMP(string pattern, string target)
{
int m = pattern.length();
int n = target.length();
int f[m];
preKMP(pattern, f);
int i = 0;
int k = 0;
while (i < n)
{
if (k == -1)
{
i++;
k = 0;
}
else if (target[i] == pattern[k])
{
i++;
k++;
if (k == m)
return 1;
}
else
k = f[k];
}
return 0;
}

int main()
{
string tar = "san and linux training";
string pat = "lin";
if (KMP(pat, tar))
cout<<"'"<<pat<<"' found in string '"<<tar<<"'"<<endl;
else
cout<<"'"<<pat<<"' not found in string '"<<tar<<"'"<<endl;
pat = "sanfoundry";
if (KMP(pat, tar))
cout<<"'"<<pat<<"' found in string '"<<tar<<"'"<<endl;
else
cout<<"'"<<pat<<"' not found in string '"<<tar<<"'"<<endl;
return 0;
}

REFERENCE

https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm
http://www.ituring.com.cn/article/59881
http://www.sanfoundry.com/cpp-program-implement-kruth-morris-patt-algorithm-kmp/