[此贴子已经被作者于2006-9-5 22:12:30编辑过]

ＫＭＰ算法是用来查找一个字符串里的子串．
至于思想我也忘啦，很久之前写过，不过没了，论坛里也有，
我记得yuki大哥曾经写过一个。你找找，要不然去看看书，数据结构的书很多都有。

数据结构精华贴
sky的!

上面那个地址不是我写的那个

这个才是

http://www.bc-cn.net/bbs/dispbbs.asp?boardID=179&ID=77190&page=2

首先感谢大家对我的帮助和鼓励,我用了N天时间,看了N本<<数据结构>>书,看了N个源码,写了N张白纸,网上查了N个资料,进入了N个论坛……，终于水落石出，啊！彻底明白了。代码中的关键是求next函数的值，在求next函数的值是关键是明白并记住这个公式： next[j+1]=next[j]+1
例如下面一个模式串：
j= 1 2 3 4 5 6 7 8 9
模式串： a b c a a b a b c
next[j]: 0 1 1 1 2 2 3 2 3

通过这个实例来说明一下如何求得next的值：

我们可以用肉眼看出next的值的：假如模式串第7个字符a与主串s中的字符s[i]不匹配时，那么主串中s[i]字符应与模式串中的哪一个字符比较呢？我们可以从模式串中看出，j7前面的串j5,j6(即a,b),和j1,j2（即a,b，要从头开始数)相等，注意要找长度最长的串，下一步，那么我们就要把j1,j2,j3 移到j5,j6,j7的位置，也就是把j3,移到j7的位置，到此为止我们就求出j7的next值是3, 当然，计算机是不可能这样做的，假如，j6(b)和j2(b)相比较，可知，j6=j2,这时就用到上面的式子，next[6+1]=next[6]+1
因为计算机是从j1到j9顺序求得next 的值的，所以，next[6+1]=2+1=3
然后我们再把j7同j3相比较,可知，j7!=j3,这时，要把j1,j2,j3当作j1,j2……j9，的子串，也就是求子串j1,j2,j3中next[j3]的值，求得的值 K'，把j[k']再同j7相比较，如果相同，就用式子next[j+1]=next[j],求出j8的值，如果不相等，再next[K']的值，……直到j=0为止，然后，j++,i++

最好把求next值的函数多运行几遍，一步一步求得next的值，再结合教程，定能够找出规律，现在我给出求next值的代码：

void getnext()//为简便没给出参数
{
int i=1,j=0;
next[1]=0;
while(i<t[0])//t[0]内是字符串t中字符的个数
{
if(j==0||t[i]==t[j])//如果t[i]==t[j],则next[i+1]=
{ // next[i]+1
i++; //t[i]是模式串中的字符，t[j]是
j++; //模式串中的子串中的字符，
next[i]=j;
}
else
j=next[j]; //如果t[i]!=t[j],则找next[j]的
} //值 K'，使t[i]和t[k']比较
}

小弟说的可能不是很明白，还望各位不要见笑，总之对待问题要细心，耐心，总能够解决。