动画：BM 算法中的坏字符规则与好后缀规则

淡淡的烟草味﹌ 2021-10-29 21:58 166阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

1977 年，德克萨斯大学的 Robert S. **B**oyer 教授和 J Strother **M**oore 教授发明了一种新的字符串匹配算法：**Boyer-Moore** 算法，简称 **BM 算法**。

该算法 **从模式串的尾部开始匹配**，且拥有在最坏情况下 O(N) 的时间复杂度。有数据表明，在实践中，比 KMP 算法的实际效能高，可以快大概 3-5 倍。

BM 算法中有两个核心规则，本文主要介绍这两个规则。

**定义**

**BM算法** 的一个特点是当不匹配的时候 **一次性可以跳过不止一个字符** 。即它不需要对被搜索的字符串中的字符进行逐一比较，而会跳过其中某些部分。通常搜索关键字越长，算法速度越快。它的效率来自于这样的事实：对于每一次失败的匹配尝试，算法都能够使用这些信息来排除尽可能多的无法匹配的位置。

它充分利用待搜索字符串的 **一些特征** ，加快了搜索的步骤。

那它是利用了什么特性去 **排除尽可能多的无法匹配的位置** 呢？

它是基于以下两个规则让模式串每次向右移动 **尽可能大** 的距离。

*  坏字符规则（**bad-character shift**）：当文本串中的某个字符跟模式串的某个字符不匹配时，我们称文本串中的这个失配字符为坏字符，此时模式串需要向右移动，移动的位数 = 坏字符在模式串中的位置 - 坏字符在模式串中最右出现的位置。此外，如果"坏字符"不包含在模式串之中，则最右出现位置为 -1。**坏字符针对的是文本串。**
 *  好后缀规则（**good-suffix shift**）：当字符失配时，后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置，且如果好后缀在模式串中没有再次出现，则为 -1。**好后缀针对的是模式串。**

![640?wx\_fmt=png][640_wx_fmt_png]

**坏字符规则**

坏字符出现的时候有两种情况进行讨论。

1、**模式串中没有出现了文本串中的那个坏字符**，将模式串直接整体对齐到这个字符的后方，继续比较。

![640?wx\_fmt=png][640_wx_fmt_png 1]  
![640?wx\_fmt=png][640_wx_fmt_png 2]

2、模式串中有对应的坏字符时，让模式串中 **最靠右** 的对应字符与坏字符相对。

这句话有一个关键词是 **最靠右**。

思考一下为什么是 **最靠右**？

看图！

![640?wx\_fmt=png][640_wx_fmt_png 3]  
![640?wx\_fmt=png][640_wx_fmt_png 4]  
![640?wx\_fmt=png][640_wx_fmt_png 5]  
![640?wx\_fmt=png][640_wx_fmt_png 6]

**好后缀规则**

1、如果模式串中存在已经匹配成功的好后缀，则把目标串与好后缀对齐，然后从模式串的最尾元素开始往前匹配。

![640?wx\_fmt=png][640_wx_fmt_png 7]  
![640?wx\_fmt=png][640_wx_fmt_png 8]

2、如果无法找到匹配好的后缀，找一个匹配的最长的前缀，让目标串与最长的前缀对齐（如果这个前缀存在的话）。**模式串\[m-s，m\] = 模式串\[0，s\]** 。

![640?wx\_fmt=png][640_wx_fmt_png 9]  
![640?wx\_fmt=png][640_wx_fmt_png 10]

3、如果完全不存在和好后缀匹配的子串，则右移整个模式串。

**动画描述**

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

**本文相关阅读推荐：**

[动画：浅谈什么是 Sunday 算法  
][Sunday _]

[动画：七分钟理解什么是KMP算法][KMP]

[动画：什么是 BF 算法 ][BF _]

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

![640?wx\_fmt=png][640_wx_fmt_png 11]

[640_wx_fmt_jpeg]: /images/20211029/670948af7b5347a98c825c0cb7f6593c.png
[640_wx_fmt_png]: /images/20211029/1e70dd89adb24ff1891e8a77172fcc2b.png
[640_wx_fmt_png 1]: /images/20211029/f1af6c4a979d450981cefced259dce90.png
[640_wx_fmt_png 2]: /images/20211029/6834b3530f0141c8886e2dc0697c5240.png
[640_wx_fmt_png 3]: /images/20211029/4bb1f2e1d8f54ed598d9e49d221e2277.png
[640_wx_fmt_png 4]: /images/20211029/64b5873fae7f4df5b2c17b408c5115e0.png
[640_wx_fmt_png 5]: /images/20211029/f0a9d1b2bd4d4cd8bfc8bb6d3b15fd04.png
[640_wx_fmt_png 6]: /images/20211029/9a63c2500ab9427ca88067c82e515c30.png
[640_wx_fmt_png 7]: /images/20211029/87a17c21cb1a409c99fe3992bbd9a42d.png
[640_wx_fmt_png 8]: /images/20211029/59acd93db87b4ffba67b2edad2666cfb.png
[640_wx_fmt_png 9]: /images/20211029/2b45fbba16a148f2919a33160886f95f.png
[640_wx_fmt_png 10]: /images/20211029/f396969787d641bf8af56953955d6d97.png
[Sunday _]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486028&idx=1&sn=64c25776f40f46c5e267730741024f69&chksm=fa0e65cdcd79ecdbd11882a762a91f462d80e191778e2414f7276bae09ba5c7476398868b8fe&scene=21#wechat_redirect
[KMP]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485939&idx=1&sn=b25f39b5644da92c4047bbbd9936f73c&chksm=fa0e6672cd79ef64dda0a21e23c2817edf4a64cbb75b9bed328d6519c6cd4fef36d03a4cb309&scene=21#wechat_redirect
[BF _]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485906&idx=1&sn=f00a07cbca83d345cbacc327e335de2d&chksm=fa0e6653cd79ef45a9566cd8ea947d122cfde8e1c9459332e4d7d04f06644fc7a6e81da7ee10&scene=21#wechat_redirect
[640_wx_fmt_png 11]: /images/20211029/b895d897bfbb4b94aced40d8010ea629.png