图解BM算法

         BM算法是Boyer-Moore算法的简称，由Boyer 和Moore提出。被认为在一般的应用中为最有效的字符串匹配算法。

     举例：在文本串S="A simple example"中搜索模式串T="example",BM算法是从后向前搜索首先比较S[6]和T[6]，如下图：

     匹配失败，T下标加1，继续匹配，如下图：

     这次匹配成功四个，在S[3]和T[2]相比处停下来，我们把这四个加到T前面作为辅助。如下图：

      T从T[0]跳到和S[4]，匹配从T[9]相比S[13]开始，如下图：

      上图匹配一开始就失败，T下标加1，再匹配，又失败，再加1，匹配成功，如下图：

       算法有时间再贴出来~~(PS:那天学画图没白费，今天一下子就画好了~ 嘿嘿 ^_^)

评论

5 楼 shaonanxu 2011-11-14  

4 楼 shimo 2010-09-04  

图解是错的。最后两次加1 ，根据坏字符规则实际上是直接加2跳转。

3 楼 sssider 2010-04-09  

有 Boyer-Moore Automata 相关的图解或者算法代码么?

2 楼 superjavason 2008-10-15  

匹配失败，T下标加1
应该是S下标加1吧

1 楼 haisheng 2008-07-30