誰可以給我講講你對kmp算法的理解
尤其是求next那部分... 问题点数：100、回复次数：6Top
1 楼aheadyes（）回复于 2006-06-04 01:00:16 得分 30
http://spaces.msn.com/aheadyes/blog/cns!A8067F7167BA8715!266.entry
随便瞎写的，相信书上有更严格的解释：）Top
2 楼chenhu_doc（^0^纯一狼^0^ 看书看到大笑，直到不能自已）回复于 2006-06-04 17:17:42 得分 30
在c版对kmp有很好的阐述了。。。
贴个blog在这里哦///
http://blog.csdn.net/A_B_C_ABC/archive/2005/11/25/536925.aspx
希望对楼主有帮助！！Top
3 楼chenhu_doc（^0^纯一狼^0^ 看书看到大笑，直到不能自已）回复于 2006-06-04 17:18:58 得分 0
本来在严蔚敏教授的书上就写得不是很懂的。。。
在这个blog里面，对next[]的取值的意义有很好的解释！！Top
4 楼getter（getter）回复于 2006-06-04 21:41:33 得分 0
嚴x敏的看得不太懂Top
5 楼CD2006（小英雄）回复于 2006-06-04 23:30:41 得分 30
通俗的描述算法的精髓，一边扫描，绝不回头
严的算法还是描述的很清楚的，个人感觉，只是伪代码部分与她的描述对应不好，不易理解，现将算法重新描述如下：
next[1] = 0;
for (i = 2; i <= 模式长度； i++)
{
j = i - 1;
k = next[j];
flag = false; // 第j位与第k位匹配成功的标志
while ( k >= 1 && !flag)
if (ch[j] == ch[k])
{
next[i] = k + 1;
next[j] = next[k]; // 改进版才有这句话
flag = true;
}
else k = next[k];
if (k == 0) next[i] = 1;
} // for
这就是最关键的求next[i]的值的算法，如果能和课本对着看，相信有很好的帮助
Top
6 楼yz_elys（）回复于 2006-06-05 11:05:03 得分 10
站在有穷状态自动机的角度很容易理解这个算法。Top
