| 网站首页 | 技术文章 | 下载频道 | 博客 | 编程论坛 |
 
| 技术教程首页 | 开发语言 | WEB开发 | .NET技术 | 数据库 | 操作系统 | 网页制作 |
 
 
您现在的位置: 编程中国 >> 技术教程 >> 开发语言 >> 数据结构 >> 正文
  ►  KMP的理解
KMP的理解
作者:nuciewth    阅读人次:……    文章来源:本站原创    发布时间:2007/9/22    网友评论()条
 

原帖及讨论: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数组和匹配的算法应该可以不用写下来吧,大家对着书上看就行了,关键是理解为什么它不用回朔.

 

 
文章录入:静夜思    责任编辑:静夜思 
  • 上一篇文章:

  • 下一篇文章:

  •  
    相关文章
    原创地带
    24小时热门帖子