KMP算法分析与实现_kmp算法伪代码编写

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。KMP算法的时间复杂度O(m+n)。《百度百科》

在《编译原理》第二版，第三章讲到了KMP算法，该算法可以以O(m+n)的时间复杂度从一个字符串中找到一个关键字。

首先看一个常规的查找子串的算法：

bool findSubstring(const std::string& s, const std::string subs)
{
	const int sLen = s.size();
	const int subsLen = subs.size();
	for (int n = 0; n < sLen; ++n)
	{
		int m = 0;
		while (m < subsLen && s[n + m] == subs[m]) 
			m++;

		if (m == subsLen) 
			return true;
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

以上算法从字符串s中查找subs子串，最坏算法时间复杂度是O(n * m)。

从s的第一个字符开始匹配子串subs，匹配失败，则从s的下一个字符开始重新匹配subs，直到匹配成功，返回true，匹配完所有s字符串，都没能匹配，则返回false。

举一个更加形象的例子，看一下该算法的匹配过程：

abcabceabcabcd					// 待匹配字符串
abcabcd							// 待匹配子串
------------匹配过程-------------
			a b c a b c e a b c a b c d
			     	    x		
>1  		a b c a b c d
			  x	
>2  		  a b c a b c d
				x 
>3  			a b c a b c d
				        x
>4  			  a b c a b c d
					x
>5  				a b c a b c d
					  x
>6  				  a b c a b c d
						x 
>7  					a b c a b c d
	
>8  					  a b c a b c d		// 匹配成功
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

‘x’表示所在的位置字符串和子串的字符匹配失败。

将以上例子改为KMP算法匹配，匹配过程如下：

abcabceabcabcd					// 待匹配字符串
abcabcd							// 待匹配子串
------------匹配过程-------------
			a b c a b c e a b c a b c d
			     	    x		
>1  		a b c a b c d
						x
>2  		  	  a b c a b c d
						x		
>3  					a b c a b c d
				        
>4  			  		  a b c a b c d		// 匹配成功
1
2
3
4
5
6
7
8
9
10
11
12

KMP算法与普通算法不同的是，在遇到匹配字符失败的时候，子串的匹配起始位置不再是子串的第一个字符，而是直接从子串的子串的结束位置的下一个字符开始，这里“子串的子串“要满足一个条件，借用《编译原理》中的解释来说就是：在已部分匹配的子串中找到一个既是该子串的真前缀又是该子串的后缀的子串。

1）串s的前缀（prefix）是从s的尾部删除0个或多个符号后得到的串。

2）串s的后缀（suffix）是从s的开始处删除0个或多个符号后得到的串。

3）串s的子串（substring）是删除s的某个前缀和某个后缀之后得到的串。

4）串s的真前缀，真后缀，真子串，分别是s的既不等于空串，也不等于s本身的前缀，后缀，子串。

上面例子中abcabce和abcabcd匹配，匹配到最后一个字符时，匹配失败，此时部分匹配的子串是abcabc，该子串包含一个子串abc，其中abc既是abcabc的真前缀，又是abcabc的后缀，因此，下次匹配时，不再从第一个a开始匹配，而是从第二个a开始匹配。

上面KMP的例子中还需要一个算法，就是如何在匹配失败的时候确定下次匹配时子串的开始位置。还是借用上面的例子，看一下在子串每个字符位置上匹配失败时，下次匹配的开始位置：

子串为a，ab，abc时不满足上面的条件，因此在第一个，第二个，第三个，第四个字符匹配失败时，下次匹配的位置都为0，而当第五个位置匹配失败时，已匹配的子串为abca，该子串满足条件的子串为a，因此下次匹配从位置1开始；第六个位置匹配失败时，已匹配子串为abcab，该子串也满足条件的子串为ab，因此下次匹配从位置2开始；第七个位置匹配失败时，已匹配子串为abcabc，该子串满足条件的子串为abc，因此下次匹配从位置3开始。

下面的伪代码展示的是如何计算子串在任何位置匹配失败的时候，下次匹配的位置：

t = 0;
f(1) = 0;
for(s = 1; s < n; s++)
{
    while(t > 0 && b[s + 1] != b[t + 1]) t = f(t);
    if(b[s + 1] == b[t + 1])
    {
        t = t + 1;        
        f(s + 1) = t;
    }
    else
    {
        f(s + 1) = 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

该伪代码取自《编译原理》3.4.5 图-3-19，并做了适当的修改。

上面代码是如何找到这些位置的，首先，第一个字符如果匹配失败的话，则下一个匹配位置为0，也就是下次匹配从第一个字符开始，即f(1)=0。

for循环遍历b数组中所有元素，与b[t + 1] 进行比较，t的值由0递增，当b[s + 1] != b[t + 1]时，t = f(t)，直到t变成0，或b[s + 1] == b[b + 1]，其目的就是当b[s + 1] != b[t + 1] 时找到s + 1位置的t的值，即f(s + 1) = t。

这个算法里面我觉得不好理解的就是那个while循环，为什么当 t > 0 并且b[s + 1] != b[t + 1]时，t = f(t)？

t > 0 说明已经有匹配成功的字符，比如acaacax，我们假设x是一个任意字符。

a								  t = 0		s = 1		f(1) = 0
a c 							  t = 0		s = 2		f(2) = 0
[a] c [a] 	 				 (a)  t = 1		s = 3		f(3) = 1
[a] c a [a]    			     (a)  t = 1		s = 4		f(4) = 1
[a c] a [a c] 			    (ac)  t = 2		s = 5		f(5) = 2
[a c a] [a c a]			   (aca)  t = 3		s = 6		f(6) = 3
a c a a c a x			     (?)  t = ?		s = 7		f(7) = ?
1
2
3
4
5
6
7

下面分析一下当s == 7时的情况：

if(x == a) {
	// 情况1：[a c a [a] c a a]			   (acaa)  t = 4		s = 7
}
else if(x == c){
	// 因为情况1不成立，所以t = f(t) 即f(3)，此时这个3对应的就是aca，而f(3)对应的是a，而a刚好和x前面那个字符相等，这不是偶然的，而是必然的，因为acaaca就是一种t=3的情况，第一个字符必然等于最后一个字符。有了这个规律，则t的值就是1 即f(3) ，此时我们就可以比较x和aca中的c，如果x == c，则t = 2
    // 情况2：[a c] a a c [a c]			   (ac)  t = 2		s = 7
}
else{
    // t = f(1), t的值变为0，此时x和a比较，由情况1可知x != a
	// 情况3：a c a a c a x			   ()  t = 0		s = 7
}
1
2
3
4
5
6
7
8
9
10
11

t = f(t)表明，t的值是已经完成匹配的情况。主要理解这一点，t > 0时总有b[0 ~ t] == b[(n - t) ~ n]。 因此，t = f(t) 可以快速的找到t的值使得b[s + 1] == b[t + 1]成立，否则t值继续改变，直到 b[s + 1] == b[t + 1]或者t == 0。

《编译原理》里面说该算法的时间复杂度是O(n)，但是里面这个while循环看起来好像又增加了这个复杂度。那么，如何理解这里的时间复杂度是O(n)呢？

实际上每个for循环中t最多加1，因此整个for循环结束，while循环中t = f(t)这句也顶多执行n次，如果把这里的n次摊分到每次for循环中，则这个时间复杂度O(n)就说的过去了。这里我当时也想不明白为什么，后来参考了一篇文章，里面是这样讲的，感觉也就说的通了。

下面是KMP算法的伪代码，同样来自于《编译原理》图 3-20

s = 0;
for(i = 1; i <= m; i++)
{
	while(s > 0 && a[i] != b[s + 1]) s = f(s);
	if(a[i] == b[s + 1]) s = s + 1;
	if(a == n) return "yes";
}
return "no";
1
2
3
4
5
6
7
8

以上算法和上一个算法非常的相似，但是解决的问题不一样，上一个算法是为这个算法服务的，即上一个算法解决的是给定一个s求f(s)的问题，这个算法解决的问题是在一个串种查找子串。

下面是最终的KMP算法的C++版本的实现：

bool findSubstring(const std::string& s, const std::string& subs)
{
	// 首先实现子串的每个字符的对应位置计算问题
	const int n = subs.size();
 	int* pos = new int[n];
	memset(pos, 0, sizeof(int) * n);
	pos[0] = 0;
	int t = 0 ;
	for (int i = 1; i < n; ++i)
	{
		while (t > 0 && subs[i] != subs[t])
		{
			t = pos[t - 1];
		}
		if (subs[i] == subs[t])
		{
			t += 1;
			pos[i] = t;
		}
		else
		{
			pos[i] = 0;
		}
	}

	// 查找子串
	const int m = s.size();
	t = 0;
	bool findSubs = false;
	for (int i = 0; i < m; ++i)
	{
		while (t > 0 && s[i] != subs[t])
		{
			t = pos[t - 1];
		}
		if (s[i] == subs[t])
		{
			t += 1; 
		}
		if (t == n)
		{
			findSubs = true;
			break;
		}
	}
	delete[] pos;
	return findSubs;
}
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

参考：KMP算法详解