KMP算法

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;
}