BM 算法全称 Boyer-Moore 算法。它是一种非常高效的字符串匹配算法，有实验统计，它的性能是著名的KMP 算法的 3 到 4 倍。下面我们来讨论一下它是如何实现这么高的效率的。
BM 算法核心思想
我们把模式串和主串的匹配过程，看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时，BF 算法和 RK 算法的做法是，模式串往后滑动一位，然后从模式串的第一个字符开始重新匹配。举个例子:
主串: a b c d s a b d f n
模式串: a b d
滑动后: a b d在这个例子里，主串中的 'c'，在模式串中是不存在的，所以，模式串向后滑动的时候，只要 'c' 与模式串有重合，肯定无法匹配。所以，我们可以一次性把模式串往后多滑动几位，把模式串移动到 'c' 的后面:
主串: a b c d s a b d f n
模式串: a b d
滑动后: a b d根据这个例子，很容易想到: 如果我们有办法找出一种规律，每次让模式串多向后滑动几位，那么匹配的效率不久大幅提升了吗？
本篇文章所探讨的 BM 算法，本质上其实就是在寻找这种规律。借助这种规律，在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。
BM 算法原理分析
BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）。我们下面依次来探讨一下，这两个规则都是怎么工作的。
坏字符规则
之前学习的 BF 算法和 RK 算法在匹配的过程中，都是按模式串的下标从小到大的顺序，依次与主串中的字符进行匹配的。这种匹配顺序比较符合我们的思维习惯，而 BM 算法的匹配顺序比较特别，它是按照模式串下标从大到小的顺序，倒着匹配的:
主串: a b c d s a b d f n
模式串: a b d
匹配顺序: 1 2 3我们从模式串的末尾往前倒着匹配，直到我们发现某个字符没法匹配的时候。我们把这个没有匹配的字符叫作坏字符（主串中的字符）。
主串: a b c d s a b d f n
模式串: a b d这里面主串中的 'c' 就是坏字符。我们拿坏字符 'c' 在模式串中查找，发现模式串中并不存在这个字符，也就是说，字符 'c' 与模式串中的任何字符都不可能匹配。这个时候，我们可以将模式串直接往后滑动三位，将模式串滑动到 'c' 后面的位置，再从模式串的末尾字符开始比较。
主串: a b c d s a b d f n
模式串: a b d
滑动后: a b d这是我们发现：模式串的最后一位 'd' 还是与主串中的字符 'a' 不匹配。那么我们还能向后滑动三位吗？答案是不行。我们很容易看出：坏字符 a 在模式串中是存在的，模式串中下标是 0 的位置也是字符 a。这种情况下，我们可以将模式串往后滑动两位，让两个 a 上下对齐，然后再从模式串的末尾字符开始，重新匹配。
主串: a b c d s a b d f n
模式串: a b d
滑动后: a b d那么新的问题来了：第一次出现坏字符的时候，我们向后滑动了三位; 第二次出现坏字符的时候我们却只向后滑动了两位。那么这其中有没有什么规律呢？
当发生不匹配的时候，我们把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作 xi。如果不存在，我们把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi。
主串: a b c d s a b d f n
模式串: a b d
xi=0 si=2这里需要说明一下：如果坏字符在模式串里多处出现，那我们在计算 xi 的时候，选择最靠后的那个，因为这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过。
利用坏字符规则，BM 算法在最好情况下的时间复杂度非常低，是 O(n/m)。比如，主串是 aaabaaabaaabaaab，模式串是 aaaa。每次比对，模式串都可以直接后移四位，所以，匹配具有类似特点的模式串和主串的时候，BM 算法非常高效。
不过，单纯使用坏字符规则还是不够的。因为根据 si-xi 计算出来的移动位数，有可能是负数，比如主串是 aaaaaaaaaaaaaaaa，模式串是 baaa。不但不会向后滑动模式串，还有可能倒退。所以，BM 算法还需要用到“好后缀规则”。
好后缀规则
好后缀规则和坏字符规则思路很相似。举个例子:
主串: a b c d s a d b b c c a b d c d
模式串: a b c d a b c 可以看到：模式串和主串有 2 个字符是匹配的，倒数第 3 个字符发生了不匹配的情况。这个时候该如何滑动模式串呢？当然，我们还可以利用坏字符规则来计算模式串的滑动位数，不过，我们也可以使用好后缀处理规则。两种规则如何抉择放在后面讲吧，这里我们先看看好后缀规则是如何做的:
我们把已经匹配的 bc 叫作好后缀，记作{u}。我们拿它在模式串中查找，如果找到了另一个跟{u}相匹配的子串{u*}，那我们就将模式串滑动到子串{u*}与主串中{u}对齐的位置。
主串: a b c d s a d b b c c a b d c d
模式串: a b c d a b c
滑动后: a b c d a b c如果在模式串中找不到另一个等于{u}的子串，我们就直接将模式串，滑动到主串中{u}的后面，因为之前的任何一次往后滑动，都没有匹配主串中{u}的情况。
主串: a b c d s a d b b c c a b d c d
模式串: a d c d a b c
滑动后: a d c d a b c不过直接将模式串向后滑动到主串中{u}的后面就可以了吗？举个例子：
主串: a b c d s a d b b a d c d a b a d
模式串: a d c d a b a 这时候如果我们将模式串直接滑到 {u} 之后的位置，我们就会错过匹配的情况:
主串: a b c d s a d b b a d c d a b a d
模式串: a d c d a b a
过度滑动: a d c d a b a
合理滑动: a d c d a b a所以，针对这种情况，我们不仅要看好后缀在模式串中，是否有另一个匹配的子串，我们还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。
所谓某个字符串 s 的后缀子串，就是最后一个字符跟 s 对齐的子串，比如 abc 的后缀子串就包括 c, bc。所谓前缀子串，就是起始字符跟 s 对齐的子串，比如 abc 的前缀子串有 a，ab。我们从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，假设是{v}，然后将模式串滑动到前缀对齐的情况。
那么坏字符规则和好后缀规则都分析的差不多了，下面就是如何实现的问题了。
BM算法代码实现
BM算法类
我将这个算法封装成了一个类。所以先放出类的声明:
class BM
{
private:
string ptrn; // 模式串
int skip[SIZE] = {}; // 坏字符表
vector<int> suffix; // 好后缀表
vector<bool> prefix; //前缀子串
void generate_skip(); // 建立坏字符表
void generate_suffix(); // 建立好后缀表
int shift_by_good_suffix(const int& begin);
public:
BM();
explicit BM(const string& p);
~BM();
void set_pattern(const string& p);
int find(const string& main_string, const int& pos = 0);
};坏字符规则实现
“坏字符规则”本身不难理解。当遇到坏字符时，要计算往后移动的位数 si-xi，其中 xi 的计算是重点，我们如何求得 xi 呢？或者说，如何查找坏字符在模式串中出现的位置呢？
如果每次都要遍历一遍查找 xi 的话，那算法的效率就会变得很低。所以我们可以事先进行一个预处理，建立一个哈希表来记录坏字符对应的 xi。
这里我建立一个最简单的哈希表，也就是将 256 个字符的位移都记录下来:
/**
* \brief 生成坏字符预处理表
*/
void BM::generate_skip()
{
// 初始化坏字符表为模式串的长度
std::fill(skip, skip + SIZE, -1);
// 从小到大的顺序可以在同一字符多次出现的时候以最靠右的那个字符到尾部距离为最终的距离
for (auto i = 0; i < ptrn.length(); i++)
skip[ptrn[i]] = i;
}好后缀规则实现
好后缀规则应该是 BM 算法中最难理解的部分了。我们先回忆一下好后缀规则的核心思想:
- 在模式串中，查找跟好后缀匹配的另一个子串；
- 在好后缀的后缀子串中，查找最长的、能跟模式串前缀子串匹配的后缀子串；
如果不考虑效率的话，这两部分都可以用暴力的方法解决。但如果不考虑效率，我为什么不用 BF 算法呢？所以我们需要一些技巧来完成这两个操作。
因为好后缀也是模式串本身的后缀子串，所以，我们可以在模式串和主串正式匹配之前，通过预处理模式串，预先计算好模式串的每个后缀子串，对应的另一个可匹配子串的位置。下面我们就来讨论一下这个预处理如何实现。
首先，如何表示模式串中不同后缀的子串呢？我们很容易看出，同一模式串的后缀子串最后一个字符的位置是固定的，所以我们可以用长度来作为一个后缀子串的标识:
| 模式串：a s d a s d | |
|---|---|
| 后缀子串 | 长度 |
| d | 1 |
| s d | 2 |
| a s d | 3 |
| d a s d | 4 |
| s d a s d | 5 |
现在，我们要引入最关键的变量 suffix 数组。suffix 数组的下标 k，表示后缀子串的长度，下标对应的数组值存储的是，在模式串中跟好后缀{u}相匹配的子串{u*}的起始下标值。举个例子:
模式串： a s d a s d
编号: 0 1 2 3 4 5
| 后缀子串 | 长度 | suffix |
|---|---|---|
| d | 1 | suffix[1] = 2 |
| s d | 2 | suffix[2] = 1 |
| a s d | 3 | suffix[3] = 0 |
| d a s d | 4 | suffix[4] = -1 |
| s d a s d | 5 | suffix[5] = -1 |
那么这样是否就可以实现好后缀规则了呢？之前讨论核心思想的时候讲过，我们不仅要在模式串中，查找跟好后缀匹配的另一个子串，还要在好后缀的后缀子串中，查找最长的能跟模式串前缀子串匹配的后缀子串。
所以我们还需要一个 bool 类型的数组，来记录模式串的后缀子串是否可以匹配其前缀子串。
模式串： a s d a s d
编号: 0 1 2 3 4 5
| 后缀子串 | 长度 | suffix | prefix |
|---|---|---|---|
| d | 1 | suffix[1] = 2 | prefix[1] = false |
| s d | 2 | suffix[2] = 1 | prefix[2] = false |
| a s d | 3 | suffix[3] = 0 | prefix[3] = true |
| d a s d | 4 | suffix[4] = -1 | prefix[4] = false |
| s d a s d | 5 | suffix[5] = -1 | prefix[5] = false |
接下来就是如何填充这两个数组了。这个计算非常的巧妙:
我们拿下标从 0 到 i 的子串（i 可以是 0 到 m-2）与整个模式串，求公共后缀子串。如果公共后缀子串的长度是 k，那我们就记录 suffix[k]=j（j 表示公共后缀子串的起始下标）。如果 j 等于 0，也就是说，公共后缀子串也是模式串的前缀子串，我们就记录 prefix[k]=true。
代码实现如下:
/**
* \brief 生成好后缀和前缀子串预处理表
*/
void BM::generate_suffix()
{
const int len = ptrn.length();
// 初始化
for (auto i = 0; i < len; i++)
{
suffix[i] = -1;
prefix[i] = false;
}
// 遍历找出所有公共后缀子串
for (auto i = 0; i < len - 1; i++)
{
int j = i; // 公共后缀子串子串的起始位置
int suffix_len = 0; // 后缀子串长度
// 求公共后缀字串，同时记录公共后缀字串的位置
while (j >= 0 && ptrn[j] == ptrn[len - 1 - suffix_len])
suffix[++suffix_len] = j--;
// 如果公共后缀子串也是模式串的前缀子串
if (j == -1)
prefix[suffix_len] = true;
}
}这两个数组处理完后，我们就可以讨论遇到不能匹配的字符时，如何根据好后缀规则计算模式串往后滑动的位数了。
假设好后缀的长度是 len。我们先拿好后缀，在 suffix 数组中查找其匹配的子串。如果 suffix[len] 不等于 -1（-1 表示不存在匹配的子串），那我们就将模式串往后移动 pos-suffix[len]+1 位（pos 表示坏字符对应的模式串中的字符下标）。如果 suffix[len] 等于 -1，表示模式串中不存在另一个跟好后缀匹配的子串片段。我们可以用下面这条规则来处理:
- 令模式串的长度为 plen。好后缀的后缀子串 b[r, plen-1]（其中，r 取值从 pos+2 到 plen-1）的长度 len=plen-r，如果 prefix[len] 等于 true，表示长度为 len 的后缀子串，有可匹配的前缀子串，这样我们可以把模式串后移 r 位。
- 如果两条规则都没有找到可以匹配好后缀及其后缀子串的子串，我们就将整个模式串后移 plen 位。
这一段也不是很好理解。解释一下这个 r 从 pos+2 开始是因为 pos 是坏字符的下标，所以好后缀的长度应该是 plen - 1 - (pos + 1)，也就是 plen - (pos + 2)。所以 r 要从 pos+2 开始。
代码实现:
/**
* \brief 由好后缀规则得到的位移数
* \param pos 坏字符对应模式串中的字符下标
*/
int BM::shift_by_good_suffix(const int& pos)
{
// 好后缀长度
int len = ptrn.length() - 1 - pos;
// 模式串中还存在和好后缀一样的子串
if (suffix[len] != -1)
return pos - suffix[len] + 1;
for (auto r = pos + 2; r < ptrn.length(); r++)
{
// 如果好后缀有可匹配的前缀子串
if (prefix[ptrn.length() - r] == true)
return r;
}
// 没有前缀子串则移动整个模式串的字节数
return ptrn.length();
}BM查找实现
实现了两种规则之后，查找就很好写了:
/**
* \brief BM算法寻找模式串
* \param main_string 主串
* \param begin 寻找的起始位置, 默认为0
* \return 模式串在主串中的下标, -1 表示未找到
*/
int BM::find(const string& main_string, const int & begin)
{
const int plen = ptrn.length(); // 模式串长度
const int mlen = main_string.length(); // 主串长度
for (auto i = begin; i <= mlen - plen; )
{
int pos;
// 从后向前匹配
for (pos = plen - 1; pos >= 0; pos--)
{
// 找到坏字符对应的下标
if (main_string[i + pos] != ptrn[pos])
break;
}
// 匹配成功
if (pos < 0)
return i;
// 坏字符规则的位移
int bad_shift = pos - skip[static_cast<int>(main_string[i + pos])];
int good_shift = 0; // 好后缀规则的位移
if (pos < plen - 1)
good_shift = shift_by_good_suffix(pos);
// 向后位移两种规则中较大的数
i += std::max(good_shift, bad_shift);
}
return -1;
}整体代码 C++ 实现
BM.h
#pragma once
#include <string>
#include <vector>
#include <algorithm>
using std::string;
using std::vector;
const int SIZE = 256;
class BM
{
private:
string ptrn; // 模式串
int skip[SIZE] = {}; // 坏字符表
vector<int> suffix; // 好后缀表
vector<bool> prefix; //前缀子串
void generate_skip(); // 建立坏字符表
void generate_suffix(); // 建立好后缀表
int shift_by_good_suffix(const int& begin);
public:
BM();
explicit BM(const string& p);
~BM();
void set_pattern(const string& p);
int find(const string& main_string, const int& pos = 0);
};BM.cpp
#include "BM.h"
/**
* \brief 生成坏字符预处理表
*/
void BM::generate_skip()
{
// 初始化坏字符表为模式串的长度
std::fill(skip, skip + SIZE, -1);
// 从小到大的顺序可以在同一字符多次出现的时候以最靠右的那个字符到尾部距离为最终的距离
for (auto i = 0; i < ptrn.length(); i++)
skip[ptrn[i]] = i;
}
/**
* \brief 生成好后缀和前缀子串预处理表
*/
void BM::generate_suffix()
{
const int len = ptrn.length();
// 初始化
for (auto i = 0; i < len; i++)
{
suffix[i] = -1;
prefix[i] = false;
}
// 遍历找出所有公共后缀子串
for (auto i = 0; i < len - 1; i++)
{
int j = i; // 公共后缀子串子串的起始位置
int suffix_len = 0; // 后缀子串长度
// 求公共后缀字串，同时记录公共后缀字串的位置
while (j >= 0 && ptrn[j] == ptrn[len - 1 - suffix_len])
suffix[++suffix_len] = j--;
// 如果公共后缀子串也是模式串的前缀子串
if (j == -1)
prefix[suffix_len] = true;
}
}
/**
* \brief 由好后缀规则得到的位移数
* \param pos 坏字符对应模式串中的字符下标
*/
int BM::shift_by_good_suffix(const int& pos)
{
// 好后缀长度
int len = ptrn.length() - 1 - pos;
// 模式串中还存在和好后缀一样的子串
if (suffix[len] != -1)
return pos - suffix[len] + 1;
for (auto r = pos + 2; r < ptrn.length(); r++)
{
// 如果好后缀有可匹配的前缀子串
if (prefix[ptrn.length() - r] == true)
return r;
}
// 没有前缀子串则移动整个模式串的字节数
return ptrn.length();
}
BM::BM()
= default;
BM::BM(const string& p)
{
set_pattern(p);
}
BM::~BM()
= default;
/**
* \brief 设置模式串并初始化
*/
void BM::set_pattern(const string& p)
{
ptrn = p;
// 分配内存
suffix.resize(p.length());
prefix.resize(p.length());
// 预处理对应的表
generate_skip();
generate_suffix();
}
/**
* \brief BM算法寻找模式串
* \param main_string 主串
* \param begin 寻找的起始位置, 默认为0
* \return 模式串在主串中的下标, -1 表示未找到
*/
int BM::find(const string& main_string, const int & begin)
{
const int plen = ptrn.length(); // 模式串长度
const int mlen = main_string.length(); // 主串长度
for (auto i = begin; i <= mlen - plen; )
{
int pos;
// 从后向前匹配
for (pos = plen - 1; pos >= 0; pos--)
{
// 找到坏字符对应的下标
if (main_string[i + pos] != ptrn[pos])
break;
}
// 匹配成功
if (pos < 0)
return i;
// 坏字符规则的位移
int bad_shift = pos - skip[static_cast<int>(main_string[i + pos])];
int good_shift = 0; // 好后缀规则的位移
if (pos < plen - 1)
good_shift = shift_by_good_suffix(pos);
// 向后位移两种规则中较大的数
i += std::max(good_shift, bad_shift);
}
return -1;
}BM算法性能分析
空间复杂度
我这里实现的 BM 算法使用了三个额外的数组: skip, suffix, prefix。其中 skip 数组和字符集的大小有关；suffix 数组和 prefix 数组都和模式串的大小有关。
时间复杂度
这里实现的 BM 算法是没有做什么优化的，所以极端情况下预处理的时间会比较长。比如模式串为 aaaaaaa 这种包含许多重复字符的字符串，预处理的时间复杂度就会比较高，约为 O(n^2)。但即便如此，我在测试的时候还是比 BF 算法快上十倍左右。实际情况比较复杂，大部分时候不会退化的这么严重。
