puppy居
puppy居士
posts - 41,comments - 27,trackbacks - 0

KMP算法,每一个初学者都曾被它搞迷糊,在数据结构教材上,这个算法出现的如此之早,你怎能指望一个还没搞懂二叉树遍历的人来理解KMP呢,记得越快,忘得越快。直到多年以后回过头来看看,这才发现KMP算法如神谕般震撼了我。实在无法想象当初Knuth、Pratt、Morris三人竟然同时发现了它。


我们假设一个场景,你手上拿着一串红蓝两种颜色的珠子,墙上挂着一串更长的珠子,同样是红蓝两色的,你的任务就是找出和你手中珠子排列顺序相同的一段。


最简单也最容易想到的方法,就是从墙上第一颗开始,拿手中的珠子挨个去和墙上珠子去比,都相同那就OK了,不相同再从墙上第二颗开始,以此类推。(文章中我就不给代码了,需要代码的直接跳到正文最后去复制)


有人会想:如果我手里的珠子都是红色的,我还用这种方法,我傻呀?对,Knuth当年也是这样想的。
你看,假设你手里是连续的100颗红色珠子,墙上从第一颗开始是99颗红色珠子,那么当你比到第100颗你才发现少了一颗,你要从第二颗开始再去数一遍吗?没人会这么做,除了程序员。


当然,正常人都要从第100颗之后再去找连续的红色珠子。有了这样的觉悟,我们可以开始进入KMP算法了。


现在抛开珠子的比喻,我们开始用术语:"串",现在手上的珠子称为模式串,墙上的珠子称为主串。任务就是从主串当中寻找模式串。为了突出KMP算法的优势,我们的串都是由0和1组成的。


原始方法的最大问题就是,每当不匹配,就要回头再做比较,这个术语叫回溯。KMP算法用一种巧妙的方法避免了主串的回溯。也就是说,主串从头到尾只需要扫描一遍。(现在还没有办法连模式串都不回溯,所以下文说到回溯均指主串的回溯)


到这里,产生了两个疑问:不回溯是可能的吗?任何情况下都可以不回溯吗?
第一个问题,我们前面已经肯定了,就是某些情况下,例如连续100个1时,我们不需要回溯。
第二个问题,我们的担心是,例如前5个相同,第6个不同,难道你能直接从主串第7个开始和模式串比较?万一从第2个开始恰好和模式串匹配,你就漏掉了。


而KMP的神奇就在于,如果第6个不同,那么接下来我会拿模式串的第1个至第5个之间的一个来和主串第6个比较,至于具体是哪个,由next值决定,这个后面再说。
这个方法保险吗?何止保险,万无一失!这就证明给你看:
当第6个失配时,有五种情况:
模式串前4个与主串第6个之前的相同
模式串前3个与主串第6个之前的相同
模式串前2个与主串第6个之前的相同

模式串前1个与主串第6个之前的相同

模式串前0个与主串第6个之前的相同

无论主串与模式串如何变化,总也逃不出这五种情况,而这五种情况的后续比较方法正好就是拿模式串1至5中间的的一个来继续比较。例如前4个相同,那当然从第5个开始比较;而前面没有相同的,那自然从模式串第1个开始。


这就说明了,任何情况下,主串都不需要回溯,前提是我们拥有next值。


(等等,你忽略了一个问题,如果next值是跟主串有关系怎么办?)
(Re:之前的比较已经说明了一个问题,模式串前5个与主串是相同的,主串这部分已经没有利用价值了,就算要回溯我在模式串上进行就可以了,这个解释总该满意了吧?)


好了,KMP算法可以开始工作了。
方法如下:
1 一开始还像原始方法那样,挨个比较。
2 等失配时,假设这时是主串的第i个,模式串的第j个,拿模式串的next(j)个继续和主串第i个进行比较
2.1 如果相同,那么再挨个比下去
2.1 如果不同,那么重复步骤2
3 比到模式串的最后一位仍然相同,则完成任务
4 比到主串的最后一位仍然未完成任务,则放弃


第2步的next(j)我们看做是一个函数,你不要管它为什么这样神奇,总之如果它能告诉你究竟是哪一个,你就只管用就没错了。


呵呵,看起来仿佛是神的指引呀:你只管比,出错了让神来告诉你由哪一个接着比。
这就是KMP算法了。打完收功。

 


-----------------------------------------------
(但是,还没有说next(j)怎么出来的呀,这样也行啊?)
其实next(j)的求法才是KMP算法最关键的地方,要理解了它,才算是理解了KMP呀!
我们来探索一下next(j)内部的原理。
前面已经提到,其实next(j)与主串一点关系也没有,这告诉我们,只需要模式串就能生成next(j)。
这么说,next(j)的值完全可以看成一个函数,它的自变量是模式串和失配位置j。
假设某一个模式串里,next(6) = 3的话,这意味着什么呢?
就是说如果第6个位置失配了,那么我直接拿模式串第3个来和主串第6个比较,之所以能这么比,只有可能是模式串的第1、2个和主串的第4、5个是匹配的,但是主串的4、5个和模式串的4、5个也是匹配的,由相等关系的传递性,我们得知模式串的1、2个和4、5个是匹配的。


这给了我们提示,如果模式串内部存在相同的片段,例如123和345相同,或者12和56相同等等这样的情况,那么我们就可以在后一个相同片段的结束出失配时,从前一个相同片段的结束处继续比较。
而如果不存在相同的片段,那么就说明主串失配位置之前的部分不会再有匹配了(否则矛盾了),我们可以从主串失配位置的后一个位置继续比较了。


这样的一对相同片段恰好要从模式串的第一个开始,这样给了我们便利,只需要:
模式串第1个和第2个开始依次比较,

然后第1个和第3个开始依次比较,然后是第1个和第4个,依次类推,就能找到全部可能的相同片段了。
凑巧,这也恰好是一个找寻模式串的任务,自己既是主串又是模式串。
上述的自我比较过程中,在每一次比较相同时,我们都可以记下一个next值,
而出现失配时,我们从主串的下个位置重新开始比,等等,想起什么来了,对,主串不需要回溯。我们不是记下了前一个next值吗?
而如果第一次就不同呢,所以我们进行一个规定,next(1)=0,next(2)=1,这样在第1个和第2个比较时,next(2)的值已经有了,随后每一个比较都已经有了当前位置的next值了。这里next值为0是表示失配位置前不可能有匹配了,这时主串从失配位置的后一个继续比,而这个位置的next值我们同样记为0。


这样看起来,寻找next值的过程和KMP本身比较的过程何其相似呀!
不过我们注意到一点,它们并不需要相似,实际上求next值的过程不用KMP方法,用原始方法一样可以求出来,但是要麻烦一些,需要后一趟比较不要把前一趟记下的next值覆盖了。


至此KMP算法的精髓应该介绍完了吧,还剩下最后一点,就是所谓的next修正值。
这个是在求next值的过程中修正的,不修正也不影响匹配结果,修正算是一种优化吧!
具体说来,修正是这么回事:


如果在j出失配时,不是要跳到next(j)吗?而如果又失配了,不是要跳到next(next(j))吗,如果又失配,就跳到next(next(next(j)))……
为了省略不停的跳的过程,我们注意到,如果第j个和第next(j)个是相同的,那么j失配了,next(j)一定失配。既然这样,那又何必再比呢,所以计录next值的时候,就判断一下是否相同,如果相同,就直接使用上一个next值。


至此,KMP算是全部结束完毕了。代码网上满天飞,我这就不给了。

本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/oyd/archive/2008/10/20/3110435.aspx

posted on 2011-04-20 11:39 puppy 阅读(154) 评论(0)  编辑 收藏 引用 所属分类: 数据结构&算法
只有注册用户登录后才能发表评论。