当前位置：首页 > news >正文

我的KMP实现

news 来源：原创 2024/5/2 16:21:20

前言

之前在搞ACM的时候了解过KMP，可是最近发现细节记不清楚了，索性重新看一遍这些基础的算法，我们先来看一下定义：“KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）”。这里对KMP的定义是字符串匹配算法，当然这个算法不仅仅是用来处理字符串的，你可以应用于查找子序列的各种问题中。

KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息，将时间复杂度从暴力匹配的O(mn)优化成了O(m+n)。现在我处于的状态是一个知其然也知其所以然的状态，也就是说知道KMP算法为什么要这样做，但是我确实没办法给第二个人讲得清清楚楚，简单来说还是功力不够，等我再练练一定给大家简单的讲一下。

内容

既然看了一天的算法总得有点收获，所以今天我决定根据自己的理解来实现以下KMP算法，代码如下，有什么不正确的地方欢迎大家指出来

KMP使用实例

#include 
  
   
#include 
   
    
#include 
    
     


bool getNext(const char* pPattern, int* pNext, int nSize)
{
	if (NULL == pPattern)
		return false;

	const int nPatternLen = strlen(pPattern);
	if (nPatternLen >= nSize)
		return false;

	// 初始化第一个元素的字符串的前缀和后缀公共部分的最大长度
	pNext[0] = pNext[1] = 0;

	// 已经匹配的元素个数
	int nMatchCount = 0;
	for (int nIndex = 1; nIndex < nPatternLen; ++nIndex)
	{

		// 遇到不匹配的元素递归处理找到最长的匹配子串
		while (nMatchCount > 0 && pPattern[nMatchCount] != pPattern[nIndex])
			nMatchCount = pNext[nMatchCount];

		if (pPattern[nMatchCount] == pPattern[nIndex])
			++nMatchCount;

		pNext[nIndex + 1] = nMatchCount;

	}

	return true;
}

// 返回找到的位置索引，未找到范返回-1
int findMatch(const char* pSrcContent, const char* pPattern)
{
	if (NULL != pSrcContent && NULL == pPattern)
		return -1;

	int nPatternLen = strlen(pPattern);
	int nSrcContentLen = strlen(pSrcContent);
	if (nSrcContentLen < nPatternLen)
		return -1;

	int* pNext = new int[nPatternLen + 1];
	if (NULL == pNext)
		return -1;

	if (!getNext(pPattern, pNext, nPatternLen + 1))
	{
		delete pNext;
		return -1;
	}

	// 匹配的个数
	int nMatchCount = 0;
	for (int nIndex = 0; nIndex < nSrcContentLen; ++nIndex)
	{
		// 发现不匹配
		while (nMatchCount > 0 && pSrcContent[nIndex] != pPattern[nMatchCount])
			nMatchCount = pNext[nMatchCount];

		if (pSrcContent[nIndex] == pPattern[nMatchCount])
			++nMatchCount;

		if (nPatternLen == nMatchCount)
		{
			return nIndex + 1 - nPatternLen;
		}
	}

	return -1;
}


int main()
{
	char szA[] = "aaaasdfhasidfahakfambfjawefjghfka";
	char szB[] = "fam";

	int nRet = findMatch(szA, szB);

	if (nRet < 0)
	{
		printf("find %s in %s postion : not find\n", szB, szA);
	}
	else
	{
		printf("find %s in %s postion : %d\n",szB, szA, nRet);
	}

	system("pause");
	return 0;
}

运行结果

find fam in aaaasdfhasidfahakfambfjawefjghfka postion : 17

总结

这个算法最主要的就是实现next函数，也就是找到模板串中每个字符的前串的前缀和后缀公共部分的最大长度。
在查找过程中要注意算法含义的转化，其中所说的模板串向后移动在代码中的实现看起来并不像移动，但含义是相同的。
注意计算next函数和查找过程中不断分割子串的操作，我个人感觉这句代码while (nMatchCount > 0 && pPattern[nMatchCount] != pPattern[nIndex]) nMatchCount = pNext[nMatchCount];是KMP算法中最精妙的部分了，学习算法时要注意这句的理解。