# 25 字符串匹配之 BM 算法 最优匹配的 BM 算法 ## 1. BM 算法 本节我们继续介绍另一个高效的字符串匹配算法 BM(Boyer-Moore)。BM 与 KMP 优化思路类似，都是希望尽可能增加发生不匹配时，模式串后移的位数来提高字符串的匹配效率。BM 要想达到更高的匹配效率，必需利用更多的已知信息。 这里依旧推荐阮一峰老师有关 [BM](http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html)算法的博客。因为阮一峰老师讲的已经不能在通俗易懂，这里我就简单总结一下 BM 算法所使用的匹配规则。示例采用博客中的示例，即在"HERE IS A SIMPLE EXAMPLE"，中搜索 "EXAMPLE"。 ### 1.1 坏字符规则 ![br_start](/images/algo/string/br_start.png) 开始匹配时，主串与模式串头部对齐，`从尾部开始比较`。此时"S"与"E"不匹配。我们称"S"为"坏字符"（bad character），即不匹配的字符。 利用坏字符以及坏字符是否出现在模式串中，BR 算法使用的第一个移位规则被称为`坏字符规则: 后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置`。如果"坏字符"不包含在搜索词之中，则上一次出现位置为 -1。道理很显而易见，如果出现坏字符，我们就直接把模式串移动到能跟坏字符匹配的位置上来。 示例中"S"不包含在搜索词"EXAMPLE"之中，这意味着可以把搜索词直接移到"S"的后一位 ![br_2](/images/algo/string/br_2.png) ### 1.2 好后缀规则 借鉴 KMP 算法，利用已经匹配的字符串和已匹配部分是否出现在模式串中，BR 算法使用的第二个移位规则被称为 `好后缀规则:后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置` - "好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"EF"是好后缀，则它的位置以"F"为准，即5（从0开始计算）。 - 如果"好后缀"在搜索词中只出现一次，则它的上一次出现位置为 -1。比如，"EF"在"ABCDEF"之中只出现一次，则它的上一次出现位置为-1（即未出现）。 - 如果"好后缀"有多个，则除了最长的那个"好后缀"，其他"好后缀"的上一次出现位置必须在头部。比如，假定"BABCDAB"的"好后缀"是"DAB"、"AB"、"B"，请问这时"好后缀"的上一次出现位置是什么？回答是，此时采用的好后缀是"B"，它的上一次出现位置是头部，即第0位 道理也很显而易见，如果已经匹配的部分多次出现在模式串，当发生不匹配时，就直接把模式串移动到上一次匹配的位置上。显然 BM 与KMP 不同，BM 不要求后缀匹配的部分必需是模式串的前缀。 ![br_3](/images/algo/string/br_3.png) "MPLE"与"MPLE"匹配。我们把这种情况称为"好后缀"（good suffix），即所有尾部匹配的字符串。注意，"MPLE"、"PLE"、"LE"、"E"都是好后缀。此时，所有的"好后缀"（MPLE、PLE、LE、E）之中，只有"E"在"EXAMPLE"还出现在头部，所以后移 6 - 0 = 6位。 ![br_4](/images/algo/string/br_4.png) ### 1.3 移位选择 Boyer-Moore算法的基本思想是，每次后移这两个规则之中的较大值。更巧妙的是，这两个规则的移动位数，只与模式串有关，与主串无关。因此，可以预先计算生成《坏字符规则表》和《好后缀规则表》。使用时，只要查表比较一下就可以了。 ## 2. 实现 显然 BR 算法的核心是要先生成《坏字符规则表》和《好后缀规则表》，然后利用这两个规则表进行字符串匹配。 ### 2.1 坏字符规则表 ### 2.2 好后缀规则表 ### 2.3 字符串匹配 **参考:** - [王争老师专栏-数据结构与算法之美](https://time.geekbang.org/column/126) - [阮一峰-Boyer-Moore算法](http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html) - [《数据结构与算法：python语言实现》](https://book.douban.com/subject/30323938/)