本文作者:佚名

模式匹配KMP

佚名 2019-04-03 758
摘要:字符串朴素模式匹配算法的2种实现://1.朴素的模式匹配算法,用while实现int StrStr_While(const char* pStr, const char* pSub,


字符串朴素模式匹配算法的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}


未经允许不得转载:

作者:佚名,标题:模式匹配KMP,原文地址:https://www.vfjianzhan.com/asp/76878.html发布于2019-04-03
转载或复制请以超链接形式并注明出处DESTOON

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏