CWYAlpha

Just another WordPress.com site

Thought this was cool: 数据结构重读 – KMP串匹配算法

leave a comment »


设:m是模式串pattern的长度,n是主串长度

传统的字符串匹配(暴力法)的时间复杂度是O(n*m)。

而KMP串匹配算法可以将时间复杂度降为O(n+m),这需要一个额外的预处理O(m)。

KMP优化的地方在于:当出现字符失配的情况时,无需回溯i指针,而是利用已经匹配的部分,将模式串尽可能向右滑动一部分。

实际上:KMP的预处理本身就是一个模式串pattern“自我匹配”的过程。因此,预处理和kmp算法主体非常神似。

预处理过程:

int get_next(char* p, int* next)
{
	int len = strlen(p);	
	int i = 0, k = -1;
	next[0] = -1;
	while(i<len)
	{
		if(k==-1 || p[i]==p[k])
		{
			i++;
			k++;
			next[i] = k;
		}else
		{
			k = next[k];
		}
	}
}

KMP匹配算法,这里我们和书上的做了一点改进,加入了一个start,即可以支持在主串中查找多次模式串。代码如下:

int kmp_index(char* s, char* p, int* next, int start)
{
	int i=start,j=0;
	int slen = strlen(s);
	int plen = strlen(p);
	while(i<slen && j<plen)
	{
		if(j==-1 || s[i]==p[j])
		{
			i++;
			j++;
		}else
		{
			j = next[j];
		}
	}
	if(j>=plen)
	{
		return i-plen;
	}else
	{
		return -1;
	}
}

测试驱动如下:

int main()
{
	char* str = "xxabaabcacxxabaabcacdabaabcac99";
	char* pattern = "abaabcac";
	int next[MAX];
	int plen = strlen(pattern);
	int i;
	// Get next value
	get_next(pattern, next);
	for(i=0;i<plen;i++)
	{
		printf("%d ", next[i]);
	}
	printf("\n");
	// KMP Index
	i=0;
	while(i!=-1)
	{
		i = kmp_index(str, pattern, next, i);
		if(i!=-1)
		{
			printf("'%s' @ %dth of '%s'\n", pattern, i, str);
			i++;
		}
	}
	return 0;
}

 
from 四号程序员四号程序员: http://www.coder4.com/archives/3150

Written by cwyalpha

五月 18, 2012 在 5:25 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: