【字符串匹配】KMP算法和next数组的c/c++实现

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

KMP算法基本思想有许多博客都写到了，写得也十分形象，不懂得可以参考下面的传送门，我就不解释基本思想了。本文主要给出KMP算法及next数组的计算方法（主要是很多网上的代码本人（相信应该是许多人吧）看不懂，直接拿来用也是各种问题），这里的代码封装性和优化都有待考究，但是基本能实现KMP算法

http://www.cnblogs.com/c-cloud/p/3224788.html

这里提醒各位看官，while循环次数不是常见的固定次数的循环，而是动态根据实际情况将大家固认为的“一趟循环”分解成几次，看代码时留意这点，对各位看官应该有所帮助。

1.KMP的next数组生成方法。

根据链接中的15来看，可以根据搜索的字符串strKey的长度确定分析的次数（第一次显然是0），第1-len次分析的长度刚好就是左边字符个数（1-len），相应次数的前缀后最的共同元素的最长长度为对应next数组的值。

同时我们发现规律：根据前缀和后缀的特点，我们可以从每次分析的字符串（每次分析的字符串都不一样）的最后一个字符开始，向前进行字符匹配。

每次匹配成功一个字符就后缀索引backIndex-1；

每次匹配字符失败，需要判断是否已经有部分匹配的字符串，若有，应重置后缀索引backIndex=0，相应next数值为0；若无，前缀索引frontIndex+1即可

每趟大循环，如果遇到已经计算到next的相应数值则进入分析下一组（这里组的概念类似链接的第15点的分析步骤）；若遇到该组没有分析完，但是遇到了一些情况：比如说frontIndex =0,或者匹配成功一个字符，则进入大循环，但是是继续分析还没有分析完的这组

void cal_next(char * strKey, int * next, int len)
{
int calTimes = ;//计算次数 ,第一次肯定为零
int frontIndex=;//负责在前缀里边索引元素
int backIndex = ;//负责在后缀里边索引元素
//清零
for (frontIndex = ; frontIndex < len; frontIndex++)
{
next[frontIndex] = ;
}
frontIndex = calTimes-;//取得可能的最大前缀和后缀的共同元素的最长的长度0-
backIndex = calTimes-;//0-
while (calTimes<=len)
{
printf("calTimes:%d\r\n",calTimes);
printf("frontIdex:%d\r\n", frontIndex);
printf("backIdex:%d\r\n", backIndex);
while (frontIndex > && strKey[backIndex] != strKey[frontIndex ])//最多calTimes次比较
{
printf(" There is a unmatched char\r\n");
if (next[calTimes - ] != )//已经有部分字符匹配，中途出现了不匹配的字符
{
next[calTimes-] = ;
backIndex = calTimes-;//重置后缀索引
break;
}
frontIndex--;
}
if (frontIndex == && strKey[backIndex ] != strKey[])//最差的情况，一次都没有匹配成功
{
next[calTimes-] =;
calTimes++;
frontIndex = calTimes-;
backIndex = calTimes-;
printf(" There is never matched\r\n");
}
else if (frontIndex == && strKey[backIndex ] == strKey[])//最后一个字符匹配成功
{
next[calTimes - ] +=;
calTimes++;
frontIndex = calTimes-;
backIndex = calTimes-;
printf(" the last char matched\r\n");
}
else
{
if (frontIndex > && strKey[backIndex ] == strKey[frontIndex ]) //匹配成功一个
{
next[calTimes - ]++;
backIndex -= ;
frontIndex--;
printf(" a char matched\r\n");
}
}
}
}

2.KMP算法的实现

这里的实现步骤其实就是算法了步骤了，应该没有什么可讲的，基本的实现思路跟next的生成方法差不多。

void kmp(char * strText, char *strKey)
{
int *next = new int[strlen(strKey)];
//计算next 数组
cal_next(strKey,next,strlen(strKey));
//查找
int textLenght = strlen(strText);
int keyLenght = strlen(strKey);
int textIndex = ;
int keyIndex = ;
int successNums = ;
while (textIndex < textLenght)
{
while (textIndex <textLenght && strKey[keyIndex] != strText[textIndex])
{
printf(" There is a unmatched char\r\n");
if (keyIndex != )//已经匹配部分字符中途遇到不匹配的字符
{
textIndex -= next[keyIndex-];
printf(" keyIndex %d next %c\r\n", keyIndex, strText[textIndex]);
keyIndex = ;
}else
textIndex++;
}
if (textIndex == textLenght )//一个都没有匹配成功（textLenght-1 时，一定是不予strKey的“相应字符匹配”，所以才会进入textIndex++）
{
if (successNums==)
printf(" Summary: Never Matched\r\n");
else printf(" Summary: %d Matched\r\n",successNums);
}
else if (strKey[keyIndex] == strText[textIndex])//找到匹配的字符
{
keyIndex++;
textIndex++;
if (keyIndex == keyLenght)
{
keyIndex = ;
successNums++;
printf(" Summary: Matched @textIndex=%d\r\n", textIndex - keyLenght);
}
printf(" There is a Matched Char\r\n");
}
}
}