Aillieo Collection

SUBTITLE

0%

字符串匹配的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个字符BCD与pattern的起始部分不匹配，这些信息对于计算程序是可知的。如果在进行逐个字符比较的过程中，可以依据这些信息，就能够在开始下次比较时，跳过第4-6个字符，直接将游标移到第7个字符，且从target第9个字符开始比较，即#7所示的状态，则会大大降低比较次数：

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

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

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=9，pattern中游标索引位置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所示状态相同。

使用这种方法对于长度分别为m的target字符串，计算的时间复杂度为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/