KMP算法

       阅读(329)  2017-10-24 20:07:12

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。


//	求子串nextval[]数组
//	如:	
//	元素编号       0    1    2    3    4    5    6    7
//	子串           a    b    a    a    b    c    a    c
//	next值        -1    0    0    1    1    2    0    1
//	nextval值     -1    0    -1   1    0    2    -1   1
//
//	求next值,根据前一位(假如其字符为x)求后一位,如果字符x与其next值对应的字符相等则后一位在前一位的基础上加1。
//	如果不相等就根据next值继续往前找直到找到与字符x相等为止,那么就在找到的字符对应的next值基础上加1。
//	如果找到了next值为-1处还没找到,它的next值就为0.
//	步骤如下:
//	1>第0位必为-1;
//	2>第1位必为0;
//	3>第2位,前一位为b,next值为0,查看next值对应的字符为a,与它不相等所以为0;
//	4>第3位,前一位为a,next值为0,查看next值对应的字符为a,与它相等所以1;
//	5>第4位,前一位为a,next值为1,查看next值对应的字符为b,与它不相等,根据b的next值0继续往前找,找到了a与它相等,
//	  所以在b next值的基础上加1,即为1;
//	6>第5位,前一位为b,next值为1,查看next值对应的字符为b,与它相等所以在b next值的基础上加1等于2;
//	7>第6位,前一位为c,next值为2,查看next值对应的字符为a,与它不相等,继续查看a的next值0,编号0对应的字符为a还是不等,
//    同时已到达-1的位置所以为0;
//	8>第7位,前一位为a,next值为0,查看next值对应的字符为a,与它相等所以为1。
//
//	根据next值求nextval值,当前字符与其next值对应的字符进行比较,不相等则为next值,相等则为next值字符对应的next值。
//	1>第0位必为-1;
//	2>第1位字符为b,next值为0,与其next值对应的字符为a,不相等,为0;
//	3>第2位字符为a,next值为0,与其next值对应的字符为a,相等,为-1;
//	4>第3位字符为a,next值为1,与其next值对应的字符为b,不相等,为1;
//	5>第4位字符为b,next值为1,与其next值对应的字符为b,相等,为0;
//	6>第5位字符为c,next值为2,与其next值对应的字符为a,不相等,为2;
//	7>第6位字符为a,next值为0,与其next值对应的字符为a,相等,为-1;
//	8>第7位字符为c,next值为1,与其next值对应的字符为b,不相等,为1。

#include <assert.h>
#include <iostream>
using namespace std;

void GetNextValue(const char *str, int * const next_value)
{
	assert(str != NULL && next_value != NULL);

	int i = 0;
	int j = -1;
	int len = (int)strlen(str);

	next_value[i] = -1;

	while (i < len - 1)
	{
		if (j == -1 || str[i] == str[j])
		{
			++i;
			++j;
			if (str[i] != str[j])
			{
				next_value[i] = j;
			}
			else
			{
				next_value[i] = next_value[j];
			}
		}
		else
		{
			j = next_value[j];
		}
	}
}

// KMP算法求子串在父串里出现的位置(由0开始)
int KmpSearch(const char *src, const char *dest, const int *next_value)
{
	assert(src != NULL && dest != NULL && next_value != NULL);

	int i = 0;
	int j = 0;
	int src_len = (int)strlen(src);
	int dest_len = (int)strlen(dest);

	while (i < src_len && j < dest_len)
	{
		if (j == -1 || src[i] == dest[j])
		{
			++i;
			++j;
		}
		else
		{
			j = next_value[j];
		}
	}

	if (j >= dest_len)
	{
		return i - dest_len;
	}
	else
	{
		return -1;
	}
}

int _tmain(int argc, char *argv[])
{
	char src[] = "acabaabaabcacaabc";
	char dest[] = "abaabcac";

	const int count = sizeof(dest) / sizeof(dest[0]) - 1;
	int next_value[count] = {0};

	GetNextValue(dest, next_value);

	int find_pos = KmpSearch(src, dest, next_value);
	
	cout << "find pos = " << find_pos << endl;
	
	cin.get();
	return 0;
}


文章评论

Keep it simple,stupid
文章数
283
总访问量
260446
今日访问
776
最近评论

ningto : 请到next.ningto.com里发表评论。
tujiaw : 抱歉csdn code服务关闭了,这个代码我也找不到了
于淞 : 你好,这个文章的源码能分享一下吗,songsong9181@163.com,谢谢了 上面的写错了
于淞 : 你好,这个文章的源码能分享一下吗,838106303@163.com,谢谢了 上面的链接不能用了
tujiaw : 多谢多谢
essaypinglun college-paper.org : 很好的博客,赞赞
Folly : 这个实现有点奇怪,Qt为什么没有统一的比对方法。
过多s : alert("hello, world!")
tujiaw : 还不错哦
回到顶部