kmp算法的理解与实现

    KMP算法曾被我戏称为看毛片算法，当时笑喷......大三那个时候硬着头皮把算法导论的kmp算法啃完，弄懂了kmp算法

的原理，甚至还写出了代码，这几天再次温习的时候，发现忘得比较彻底。我总结，学算法不能只对着书本学理论，而应该

用自己的理解去看清算法的本质，最好用文字把你的理解记录下来，这样才能做到活学活用，而且不容易忘。写这篇博客就是想把自己这几天的思路记下来。

 

一 kmp算法为什么比传统的字符串匹配算法快

假设文本T = y1y2y3....yn， 模式 P = p1p2p3...pm， 传统的匹配算法把位移为0,1,...n-m时的文本依次跟P比较，每次比较最多花费O(m)的时间，算法的复杂度为O((n-m+1)*m)。这种算法没有利用匹配过的信息，每次都从头开始比较，速度很慢。而kmp算法充分利用了之前的匹配信息，从而避免一些明显不合法的位移。加快匹配过程。来看一个例子：

 

#########000xxxx000######                       文本T

|<---- s ---->|000xxxx000~~~                              模式P

 

假设位移为s时，T和P匹配了红色部分的字符，即匹配到了模式P的前10个字符，如果按照传统的匹配方法，下一步就是从位移s+1开始比较，而kmp算法则直接从位移s+7开始比较，而且断定：位移s+7对应的串和模式P的前3个字符是相同的，可

以不用比较，直接从第4个字符开始比较，这种跳跃式的匹配是不是比传统匹配方法快很多，如下图所示：

 

#########000xxxx000######                       文本T

|<-------- s+7-------->| 000xxxx000~~~               模式P

 

 

 

那么kmp是如何实现这种跳跃的呢？注意到红色部分的字符，即模式P的前10个字符，有一个特点：它的开始3个字符和末尾

3个字符是一样的，又已知文本T也存在红色部分的字符，我们把位移移动 10-3 = 7个位置，让模式P的开始3个字符对准文本

T红色部分的末尾3个字符，那么它们的前3个字符必然可以匹配。

 

二 构造前缀数组

 

上面的例子是文本T和模式P匹配了前面10个字符的情况下发生的，而且我们观察到模式P的前缀P10中，它的开始3个字符和末尾3个字符是一样的。如果对于模式P的所有前缀P1,P2...Pm，都能求出它们首尾有多少个字符是一样的，当然相同的字

符数越多越好，那么就可以按照上面的方法，进行跳跃式的匹配。

 

 

定义：

Pi表示模式P的前i个字符组成的前缀， next[i] = j表示Pi中的开始j个字符和末尾j个字符是一样的，而且对于前缀Pi来说，这样

的j是最大值。next[i] = j的另外一个定义是：有一个含有j个字符的串，它既是Pi的真前缀，又是Pi的真后缀

 

规定：

next[1] = next[0] = 0

 

 

next[i]就是前缀数组，下面通过1个例子来看如何构造前缀数组。

例子1：cacca有5个前缀，求出其对应的next数组。

前缀2为ca，显然首尾没有相同的字符，next[2] = 0

前缀3为cac，显然首尾有共同的字符c，故next[3] = 1

前缀4为cacc，首尾有共同的字符c，故next[4] = 1

前缀5为cacca，首尾有共同的字符ca，故next[5] = 2

 

 

 

如果仔细观察，可以发现构造next[i]的时候，可以利用next[i-1]的结果。假设模式已求得next[10] = 3，如下图所示：

 

 

000#xxx000         前缀P10

000                        末尾3个字符

 

根据前缀函数的定义：next[10] = 3意味着末尾3个字符和P10的前3个字符是一样的

为求next[11]，可以直接比较第4个字符和第11个字符，如下图所示：蓝色和绿色的#号所示，如果它们相等，则

next[11] = next[10]+1 = 4,这是因为next[10] = 3保证了前缀P11和末尾4个字符的前3个字符是一样的.

 

000#xxx000#       前缀P11

000#                      末尾4个字符

 

所以只需验证第4个字符和第11个字符。但如果这两个字符不想等呢？那就继续迭代，利用next[next[10] = next[3]的值来求

next[11]。代码如下：

 

void compute_prefix(int *next, char *p)
{
	int		i, n, k;

	n = strlen(p);
	next[1] = next[0] = 0;
	k = 0;		/* 第i次迭代开始之前，k表示next[i-1]的值 */	
	for (i = 2; i <= n; i++) {
		for (; k != 0 && p[k] != p[i-1]; k = next[k]);
		if (p[k] == p[i-1]) k++;
		next[i] = k;
	}
}

 

 

三 模拟KMP的查找过程

这里实现的算法与算法导论中的不一样，我觉得这种方法更加直观，思路就是模拟第1部分介绍的方法，每次匹配的时候

都利用上一次匹配信息，对于模式P，从第next[q]个字符开始比较，对于文本T，用一个变量s指示将要从哪个位置开始比较

，迭代开始之前，就从s这个位置开始。

 

void kmp_match(char *text, char *p, int *next)
{
	int 	m, n, s, q;

	m = strlen(p);
	n = strlen(text);
	q = s = 0;	/* q表示上一次迭代匹配了多少个字符，
				   s表示这次迭代从text的哪个字符开始比较 */ 
	while (s < n) {
		for (q = next[q]; q < m && p[q] == text[s]; q++, s++);
		if (q == 0) s++;
		else if (q == m) {
			printf("pattern occurs with shift %d\n", s-m);
		}
	}
}

 

四 测试

 

int main()
{
	int 	next[101], n;
	char	*p = "ca";
	char	*text = "cacca";

	compute_prefix(next, p);
	kmp_match(text, p, next);

	return 0;
}