模式匹配 KMP算法详解

/*
 *	KMP 模式匹配算法
 */

#include iostream
#include cstring
using namespace std;

/*
 *	计算模式串的next数组
 *	模式串既做主串，又做模式串，进行匹配
 *	时间复杂度为O(m)，m为模式串的长度
 */
void countNext(char* strPattern, int len, int* next)
{
	int i = 0, j = -1;
	next[i] = j;
	while (i  len-1)
	{
		if (j == -1)
		{
			i++;
			j++;
			next[i] = j;
		} else if (strPattern[i] == strPattern[j]) {
			i++;
			j++;
			if (strPattern[i] != strPattern[j])
			{
				next[i] = j;
			} else {
				next[i] = next[j];
			}
		} else {
			j = next[j];
		}
	}
}

/*
 *	利用KMP算法进行模式匹配
 *	KMP算法的时间复杂度为O(n)+O(m) = O(n+m)
 *	其中n为主串的长度，m为模式串的长度，需要先算出next数组
 *	KMP算法的核心就是在搜索模式串的过程中，主串的指针不会回朔
 *	只会尽可能的不断向后移，避免无效的回朔，节约了时间，适合于主串
 *	中有较多部分匹配模式串的情况，否则如果没有什么回朔，也就不需要用KMP算法了
 */
int indexKMP(char* strMain, int lenMain, char* strPattern, int lenPattern, int pos, int* next)
{
	int i = pos, j = 0;
	while (i  lenMain  j  lenPattern)
	{
		if (j == -1 || strMain[i] == strPattern[j])
		{
			i++;
			j++;
		} else {
			j = next[j];
		}
	}

	if (j = lenPattern)
	{
		return i - lenPattern;
	}

	return -1;
}


int main()
{
	char* strPattern = "abce";
	char* strMain = "ksekabcedwfabcekf";
	int lenMain = strlen(strMain);
	int lenPattern = strlen(strPattern);

	int* next = new int[lenPattern];
	countNext(strPattern, lenPattern, next);

	int startPos = 5;
	int pos = indexKMP(strMain, lenMain, strPattern, lenPattern, startPos, next);
	
	if (pos  0)
	{
		cout"从字符串 "strMain" 的第 "startPos+1" 位置开始没有找到字符串 "strPatternendl;
	} else {
		cout"从字符串 "strMain" 的第 "startPos+1" 位置开始找到字符串 "strPattern" 在第 "pos+1
				" 个位置"endl;
	}

	delete[] next;
	return 0;
}