模式匹配KMP

字符串朴素模式匹配算法的2种实现：

//1.朴素的模式匹配算法，用while实现

int StrStr_While(const char* pStr, const char* pSub, int* pos)
{
	int nRet = 0;
	int pStrLen = strlen(pStr);
	int pSubLen = strlen(pSub);
	int i = 0, j = 0;
	int nLen = pStrLen - pSubLen;

	if (pStr == NULL || pSub == NULL)
	{
		nRet = -1;
		printf("param input error!");
		return nRet;
	}

	while (i < pStrLen && j < pSubLen)
	{
		if (*(pStr + i) == *(pSub + j))
		{
			++i;
			++j;
		}
		else
		{
			i = i - j + 1;
			j = 0;
		}
	}

	if (j == pSubLen)
		*pos = i - j + 1;

	return nRet;
}

//2.朴素的模式匹配，用for循环实现

int StrStr_For(const char* pStr, const char* pSub, int* pos)
{
	int nRet = 0;
	int pStrLen = strlen(pStr);
	int pSubLen = strlen(pSub);
	int i = 0, j = 0;
	int nLen = pStrLen - pSubLen;

	if (pStr == NULL || pSub == NULL)
	{
		nRet = -1;
		printf("param input error!");
		return nRet;
	}

	for (i = 0; i <= nLen; ++i)
	{
		for (j = 0; j < pSubLen; ++j)
		{
			if (*(pStr + i + j) != *(pSub + j))
				break;
		}

		if (j == pSubLen)
		{
			*pos = i + 1;
			break;
		}
	}
	
	return nRet;
}

实现字符串的匹配有高效的算法。那就是KMP算法，实现例如以下：

//取得KMP算法须要用的的next数组

int GetNext(const char* pStr, int nNext[])
{
	int nRet = 0;
	if (pStr == NULL || nNext == NULL)
	{
		nRet = -1;
		printf("param input error!\n");
		return nRet;
	}

	int nLen = strlen(pStr);
	int i = 0, j = -1;
	nNext[i] = j;
	while (i < nLen - 1)
	{
		if (j == -1 || pStr[i] == pStr[j])
		{
			++i;
			++j;
			nNext[i] = j;
		}
		else
		{
			j = nNext[j];
		}
	}

	return nRet;
}



//取next数组的改进型算法！剔除多个反复字符的next数组值持续增长。

int GetNextVal(const char* pStr, int nNext[])

{

	int nRet = 0;

	if (pStr == NULL || nNext == NULL)

	{

		nRet = -1;

		printf("param input error!\n");

		return nRet;

	}



	int nLen = strlen(pStr);

	int i = 0, j = -1;

	nNext[i] = j;

	while (i < nLen - 1)

	{

		if (j == -1 || pStr[i] == pStr[j])

		{

			++i;

			++j;

			if (pStr[i] != pStr[j])

				nNext[i] = j;

			else

				nNext[i] = nNext[j];

		}

		else

		{

			j = nNext[j];

		}

	}



	return nRet;

}

这是针对类似aaaaaaab这种字符串使用上面两个函数取得的next数组值得比較。注意书上的都是字符串从数组的下标为1的位置開始存储的。我改进的算法是还是让字符串从数组下标为0的位置開始存储。

所以上面的next数组值都要相较与原来的值减1。

//调用上面的函数实现KMP高效字符串模式匹配算法！

int Index_KMP(const char* pStr, const char* pSub, int* nPos)
{
	int nRet = 0;
	if (pStr == NULL || pSub == NULL || nPos == NULL)
	{
		nRet = -1;
		printf("param input error!\n");
		return nRet;
	}

	int pStrlen = strlen(pStr);
	int pSublen = strlen(pSub);

	int nNext[255] = { 0 };
	//nRet = GetNext(pSub,nNext);
	nRet = GetNextVal(pSub, nNext);
	if (nRet != 0)
	{
		printf("call GetNext() func is error!\n");
		return nRet;
	}

	int i = 0, j = 0;
	while (i < pStrlen && j < pSublen)
	{
		if (j == -1 || *(pStr + i) == *(pSub + j))
		{
			++i;
			++j;
		}
		else
		{
			j = nNext[j];
		}
	}

	if (j == pSublen)
		*nPos = i - j + 1;

	return nRet;
}

本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5174879.html，如需转载请自行联系原作者