当前位置:   article > 正文

BM算法详解_如何建立坏字符表

如何建立坏字符表

1977年,Robert S.Boyer和J Strother Moore提出了另一种在O(n)时间复杂度内,完成字符串匹配的算法,其在绝大多数场合的性能表现,比KMP算法还要出色,下面我们就来详细了解一下这一出色的单模式匹配算法,在此之前推荐读者读一下我的另一篇文章《KMP算法详解》,对于透彻理解BM算法大有裨益。

在讲解Boyer-Moore算法之前,我们还是要提一提KMP算法的老例子,当模式串与目标串匹配至如下位置时:

 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
b a b c b a b c a b c a a b c a b c a b c a c a b c
          a b c a b c a c a b                      
我们发现target[13]!=pattern[7],此时根据KMP算法的next值,我们将target[13]与pattern[5]对齐,再依次执行匹配。这里target[13]='a'。如果target[13]='d',因为'd'不是模式串pattern中的字符,所以无论将target[13]与pattern中任何一个字符对齐都会匹配失败,所以当我们在匹配过程中发现target[i]是不属于模式串的字符,则我们可以直接将target[i+1],与pattern[1]对齐,再向后执行匹配。这样就获得了更大的跳转幅度,同时也能保证匹配的正确性。这便是BM算法相较于KMP算法的一个重要改进。

BM算法之所以能够在单模式匹配中有更加出色的表现,主要是其使用了两个跳转表,一个是坏字符表(论文中称为delta1),一个是好后缀表(论文中称为delta2),下面我们以BM算法对目标串的一次匹配操作,来讲解这两个表的具体跳转策略,这里模式串为"AT-THAT",目标串为"WHICH-FINALLY-HALTS.--AT-THAT-POINT"。

   1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
  W H I C H - F I N A L L Y - H A L T S . - - A T - T H A T - P O I N T
 1 A T - T H A T                                                        
 2               A T - T H A T                  
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/木道寻08/article/detail/791142
推荐阅读
相关标签
  

闽ICP备14008679号