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

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

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

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

1977 年,德克萨斯大学的 Robert S. Boyer 教授和 J Strother Moore 教授发明了一种新的字符串匹配算法:Boyer-Moore 算法,简称 BM 算法

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

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


定义


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

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

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

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

  • 坏字符规则(bad-character shift):当文本串中的某个字符跟模式串的某个字符不匹配时,我们称文本串中的这个失配字符为坏字符,此时模式串需要向右移动,移动的位数 = 坏字符在模式串中的位置 – 坏字符在模式串中最右出现的位置。此外,如果”坏字符”不包含在模式串之中,则最右出现位置为 -1。坏字符针对的是文本串。

  • 好后缀规则(good-suffix shift):当字符失配时,后移位数 = 好后缀在模式串中的位置 – 好后缀在模式串上一次出现的位置,且如果好后缀在模式串中没有再次出现,则为 -1。好后缀针对的是模式串。

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


坏字符规则


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

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

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

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

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

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

思考一下为什么是 最靠右

看图!

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

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

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

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


好后缀规则


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

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

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

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

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

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

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

动画描述






本文相关阅读推荐:


动画:浅谈什么是 Sunday 算法

动画:七分钟理解什么是KMP算法

动画:什么是 BF 算法 



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

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 动画:BM 算法中的坏字符规则与好后缀规则

我还会在以下平台发布内容

GitHub 哔哩哔哩