原帖及讨论：http://bbs.bccn.net/thread-169773-1-1.html */ --------------------------------------------------------------------------------------
*/ 出自： 编程中国 http://www.bccn.net
*/ 作者： nuciewth QQ：314218584
*/ 时间： 2007-9-13 编程论坛首发
*/ 声明： 尊重作者劳动，转载请保留本段文字
*/ --------------------------------------------------------------------------------------
今天看了一个上午的KMP,还算有点体会.拿出来一起分享一下,有什么不对的地方,请大家指正,谢谢.
前面I喜欢C斑竹 写过一个理解KMP的过程,写的蛮好,大家可以先去看一下.
假设:主串T,模式串P进行匹配,当匹配到T[r]!=P[i]时有:
[ P[0] ...P[i-1] ]=[ T[r-i] ...T[r-1] ]这两段是对应相等的.然而模式串也存在这样的匹配
[ P[0] ...P[k-1] ]=[ P[i-k]...P[i-1] ](这里的K即所谓的最长真前,后缀的大小)
很显然有:[ T[r-k] ... T[r-1]]=[ P[0] ... P[k-1] ]
这样我们就可以看出,下一次匹配应该是从 T[r]和P[k]开始比较(前面的k个字符已经匹配成功了).
所以主串不用进行回朔,提高了效率.
下面是个简单的图解,画的不好,凑合着参考一下.
此主题相关图片如下：
现在关键是怎么求出当前这一步匹配的最长真前缀大小K.其实K就是模式串的自身模式匹配.
从红色部分的定义可以看出,K就是P[I]前M个字符(后缀)与P[]的最前面的M个字符(前缀)对应相等的最大值.
(M的最大值)而每次的K就构成了next[]数组.
我们规定next[0]=-1表示下一步将从p[0]和T[r+1]开始继续比较
next[i]=
{
:-1 //i==0
:MAX{ k | 0 < k< i } //[ P[0] ...P[k-1] ]=[ P[i-k]...P[i-1] ] }
:0 //其他情况
}
我想求next数组和匹配的算法应该可以不用写下来吧,大家对着书上看就行了,关键是理解为什么它不用回朔.
|