• 数据结构与算法之KMP(串中的模式匹配算法)
  • 未来的狂人 发表于 2015/10/20 23:50:00 | 分类标签: 数据结构 算法 KMP算法
  • KMP算法是一种模式匹配算法的改进版,其通过减少匹配的次数以及使主串不回朔来减少字符串匹配的次数,从而较少算法的相应代价,但是,事件万物是普遍归中的,KMP算法的有效性也是有一定的局限的,我将在本文的最后也讨论这个算法的局限性。

    一般的匹配算法:
    KMP基本概念引入:

    但是,其实我们会发现,上面的中间两个匹配步骤是没有必要的,因为他们的第一个匹配字母就不相同,完全没有可比性,而当我们在第四次匹配的时候,其实我们从模式串中就可得知,只有当模式串滑到这个地方的时候,它的匹配才是最有价值的,因为从模式串中我们可以得知,最后一个C的前一个字母是a,而在模式串中的第二个字母b的前一个字母也是a,再无其他,从第一步匹配的结果我们可以得知,模式串中的最后一个字母c与主串中的b匹配失败(读者们是否注意到,我们前面提到的,这个c的前一个字母是a哦), 而从模式串中我们可以得知,即我们完全可以跳过上面匹配步骤的中间的两步,那是否读者在担心中间会错过原本可以匹配的呢,完全不必担心,因为在我们的模式串中就记录了,前面就连一个能和a进行匹配的字母都没有。 
      那么,当某一轮匹配失败时,模式项的滑动位置如何确定,即模式项中的那一项来和主串的的b(黄色格子内)对齐,从而省略中间的比较项,我们可以将这一项的index设置为K,如上的模式项,K为2   注意在串中,数组的第一项是用来记录数据个数的。

    -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    如上所述,KMP算法的关键,即根据模式串找到那个K(下面列出K所需要满足的条件)(当主串中第i个字符与子串中第j个字符失配时):

    设主串为:s1s2……sn  子串为:p1p2……pn

    则K的取值应满足:
    ----------------------》》》》》》》》》》》》》》》

     

    归根结底,找模式串与串头重复的子串:

    实例:

    那么:如何找到模式串中的每一个元素的K,也即如图中的next数组:

    代码敬上:
    1. void get_next(SString T,int next[])  
    2.  { /* 求模式串T的next函数值并存入数组next 算法 4.7 */  
    3.    int i=1,j=0;  
    4.    next[1]=0;  
    5.    while(i<T[0])  
    6.      if(j==0||T[i]==T[j])  
    7.      {  
    8.        ++i;  
    9.        ++j;  
    10.        next[i]=j;  
    11.      }  
    12.      else  
    13.        j=next[j];  /*精髓之处  当前面已经有了相似的比较的时候,直接借用前面的结果    两个大体的环境相似,则这两个大体的环境间就会存在相同的匹配环境,即已经记录的环境,如果错过了一些已经匹配了子串,则会导致K值比实际的要小,即后面的匹配必须依赖前面的匹配结果*/  
    14.  }  

      上面代码解释:
    1:j=0时,i和j都要相加并给next赋值
    2:T[i] = T[j] ,i和j都要相加并给next赋值

    如果上面两个都不满足,则需要将 j 往前指向,那么问题就来了,为什么不直接 j = 1,而需要将 next[j]的值赋给 j 呢,其实就如我在代码中所讲,不妨也举个栗子说明一下。
    其实可以总结为一下几点,K的目的是定位偏移量的index,失配项的前面有几个与模式项的头部相等的,K就为这些数加1,而其实这几个数,正是我们所要跳过的。

    KMP算法的劣势,其实,从寻找K的过程中我们就可以看出,KMP算法重度依赖模式列中存在重复的子串,不然~~~~~~
  • 请您注意

    ·自觉遵守:爱国、守法、自律、真实、文明的原则

    ·尊重网上道德,遵守《全国人大常委会关于维护互联网安全的决定》及中华人民共和国其他各项有关法律法规

    ·严禁发表危害国家安全,破坏民族团结、国家宗教政策和社会稳定,含侮辱、诽谤、教唆、淫秽等内容的作品

    ·承担一切因您的行为而直接或间接导致的民事或刑事法律责任

    ·您在编程中国社区新闻评论发表的作品,本网站有权在网站内保留、转载、引用或者删除

    ·参与本评论即表明您已经阅读并接受上述条款

  • 感谢本文作者
  • 作者头像
  • 昵称:未来的狂人
  • 加入时间:2013/6/13 0:00:00
  • TA的签名
  • 这家伙很懒,虾米都没写
  • +进入TA的空间
  • 以下内容也很赞哦
分享按钮