-
版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://skyofcai.blogbus.com/logs/39088627.html
KMP算法研究
KMP算法，网上有很多版本，我看了一些，大都不太满意。所以自己写了一个，跟网上的都不一样。但KMP算法的思路肯定是一样的（毕竟这算法是人家想出来的，我只是用了我个人的风格去实现，愿多提宝贵意见）。
其实KMP算法很简单，书上和网上的讲解大多都力求精细，我觉得这只能做个参考。初学者一般还是要有人来点拨和自己揣摩。现在，我搞懂了KMP算法，我就可以说出KMP算法的要害。好啦，废话少说，转入正题。
KMP算法的要害就是： GetNext()函数。它就是要获取下一个要比较的模式串中的位置。抓住这个要害不动摇，继续深究，KMP算法就逐渐明朗大白了。
具体算法分析，网上有很多，我这里指点拨，就不去复制网上的东西了（互联网上的数据冗余太多了，我不能火上浇油，制造太多垃圾）。如果读者有什么不懂的问题，可以评论的方式和我互动交流。
代码实现：
（声明： 该代码经过测试，但不能排除一切bug。任何人使用且发现bug并造成的一切损失，将由使用本代码者承担全部责任，而本作者不承担任何责任。该代码仅供学习交流。若能将bug报告给本作者，在下会感激不尽。）
#include <stdio.h>
#include <string.h>
int TrueSubStr(const char *s, int j); //判别真字串，返回非0为真字串
int GetNext(const char *s, int j); //获取下一个指针
int KMP(const char *s, const char *t); //KMP算法主体，返回主串中的位置
int main(void)
{
int k;
k = KMP ("faskjfsf", "jfa");
printf ("%d\n", k);
return 0;
}
int TrueSubStr(const char *s, int n)
{
int k = 0;
while (k<n) // 0 < k < n
if (s[k] == s[n-k])
k++;
else
break;
return k;
}
int GetNext(const char *s, int j)
{
if (j == 0)
return -1;
return TrueSubStr(s, j);
}
int KMP(const char *s, const char *t)
{
int i = 0; //i指s
int j = 0; //j指t
int k = 0; //k指模式串中下一个带比较的位置
while (s[i] != '\0' && t[j] != '\0')
{
if (s[i] == t[j])
{
i++;
j++;
}
else
{
if (j == 0)
i++;
else if ( (k = GetNext(t,j)) != 0)
j = k;
else
{
i++;
j = 0;
}
}
}//while
if (t[j] == '\0')
return (i-j);
return -1;
}//KMP
随机文章：
李春葆《数据结构教程》上机实验题4.***编码实现 2009-04-16Brute-Force算法分析与实现 2009-04-15新武昌火车站 2008-02-021219 2007-12-19我喜欢的文章（三） 2006-05-31
收藏到：Del.icio.us