学习Boyer-Moore算法

简介

1977年，R.S.Boyer和J.S.Moore发表了他们的经典论文 “A Fast String Search Algorithm”。Boyer-Moore技术展示了一种对字符串查找问题的新解决方案：它利用两种方法，使得无需检查文本中的所有字符即可查找文本变为可能。这两种方法称为启发式方法（heuristic）（即使用以前的信息来寻找解决方案的技术），它们分别是“跳过字符”和“重复模式”，也称“坏字符”和“好后缀”。现在使用的各种文本编辑器的查找功能（Ctrl+F），大多都采用Boyer-Moore算法。

接下来我们就用J.S.Moore提供的例子来学习一下。T是文本串，P是模式串，我们的目的就是在T中找到P。这里要说明一点：这里我们是倒序比较两个字符串，如果匹配失败再根据两种启发式方法来移动模式串。

1
2
3

Text T : HERE IS A SIMPLE EXAMPLE
Pattern P : EXAMPLE
           <--

坏字符（Bad Character Heuristic）

当文本 T 中的某个字符跟模式 P 的某个字符不匹配时，我们称文本 T 中的这个失配字符为坏字符。

坏字符规则：

1	模式串后移位数 = 坏字符在模式中失配的位置 - 坏字符在模式中最右边出现的位置

坏字符启发法规则中的特殊情况：

如果坏字符在模式中的位置位于失配位置的右侧，则此启发法不提供任何建议。

字符“S”出现了不匹配，如果不匹配字符不存在与模式串中，则坏字符最右出现的位置为-1，根据换字符规则移6 - (-1) = 7位。

字符“P”出现了不匹配，如果不匹配字符存在于模式串中，那么将模式串最右边出现的“P”与文本串中失配的“P”对齐，根据换字符规则有移6 - 4 = 2位。

接着看一下坏字符的代码:

//计算坏字符数组
void GetBC(string &p, int &m, int bc[]) {
    for (int i = 0; i < MAX_CHAR; i++) {
        bc[i] = m;
    }
    for (int i = 0; i < m; i++) {
        bc[p[i]] = m - 1 - i;
    }
}

有人会问MAX_CHAR是多少啊？代码里面我设置的是256。这里没考虑中文匹配，因为bc数组是用字符ASCII码作为下标来记录模式串中每个字符在最右边出现的位置（中文ASCII码太大，建议用键值对形式来存储比较好）。

好后缀（Good Suffix Heuristic）

当文本 T 中的某个字符跟模式 P 的某个字符不匹配时，我们称文本 T 中的已经匹配的字符串为后缀。

继续来看上面的匹配过程。

目前可以看到匹配到了四个字符，那么就有四个后缀：“MPLE”、“PLE”、“LE”、“E”。但是接下来出“I”和“A”不匹配，现在需要移动模式串了。

好后缀规则：

1 2	模式串后移位数 = 最长好后缀在模式中的末尾位置 - 最长好后缀在模式串中最靠近末尾的位置 PS:这里的位置通常以后缀的最后一个字符为准

后缀在模式串中除了末尾以外的位置出现过，我们称之为好后缀。我们先来找出这些后缀在模式串最靠近末尾出现的位置。

“MPLE” : 未出现；
“PLE” : 未出现；
“LE” : 未出现；
“E” : 出现在头部，最靠近末尾的位置为 0；

由于只有 “E” 在模式中出现，其当前位置为 6，上一次出现的位置为 0，则依据好后缀规则，模式后移位数为 6 - 0 = 6 位，而如果依据坏字符启发法规则，模式后移位数为 2 - (-1) = 3 位。最终后移位数选择两种方法中较大者即可。

接下来该实现代码了，首先需要一个好后缀长度算法。

从位置i向前数与模式串相同后缀的位数，代码如下：

//计算后缀数组
void Suffixes(string &p, int &m, int suff[]) {
    suff[m-1]=m;
    for (int i=m-2; i>=0; --i){
        int q=i;
        while(q>=0&&p[q]==p[m-1-i+q])
            --q;
        suff[i]=i-q;
    }
}

第一种情况

如果在i位置匹配失败，但是已匹配的后缀都只出现了一次，没有找到好后缀，这种情况默认移动整个模式串长度。

第二种情况

如果匹配到好后缀同时也是模式串的前缀的情况，可称为真好后缀。

第三种情况

如果匹配到好后缀在模式串中间。

综合三种情况，好后缀移动位数的代码是这样的:

//计算好后缀数组
void GetGS(string &p, int &m, int gs[]) {
    int suff[MAX_LENGTH];
    Suffixes(p, m, suff);
    
    //第一种情况：模式串中没有子串匹配上好后缀，也找不到一个最大前缀
    for (int i = 0; i < m; i++) {
        gs[i] = m;
    }
    
    //第二种情况：模式串中没有子串匹配上好后缀，但找到一个最大前缀
    int j = 0;
    for (int i = m - 2; i >= 0; i--) {
        if (suff[i] == i + 1) {
            for (; j < m - 1 - i; j++) {
                gs[j] = m - 1 - i;
            }
        }
    }
    
    //第三种情况：模式串中有子串匹配上好后缀
    for (int i = 0; i <= m - 2; i++) {
        gs[m - 1 - suff[i]] = m - 1- i;
    }
}

好后缀字符启发法则也存在特殊情况，如果suff[i]=0，第三种情况处理只会修改gs[m-1]的值，而失配位置出现在末尾第一位时，参考好后缀显然不可靠。
不过BM算法失配移动位数是取坏字符和好后缀中的较大值，在计算过程中两种启发法则的正常情况和特殊情况互相补充。

完整代码

#include <iostream>
#include <string>
#include <algorithm>

#define MAX_CHAR 256
#define MAX_LENGTH 1000

using namespace std;

//计算坏字符数组
void GetBC(string &p, int &m, int bc[]) {
    for (int i = 0; i < MAX_CHAR; i++) {
        bc[i] = m;
    }
    for (int i = 0; i < m; i++) {
        bc[p[i]] = m - 1 - i;
    }
}
//计算后缀数组
void Suffixes(string &p, int &m, int suff[]) {
    suff[m-1]=m;
    for (int i=m-2; i>=0; --i){
        int q=i;
        while(q>=0&&p[q]==p[m-1-i+q])
            --q;
        suff[i]=i-q;
    }
}
//计算好后缀数组
void GetGS(string &p, int &m, int gs[]) {
    int suff[MAX_LENGTH];
    Suffixes(p, m, suff);
    
    //第一种情况：模式串中没有子串匹配上好后缀，也找不到一个最大前缀
    for (int i = 0; i < m; i++) {
        gs[i] = m;
    }
    
    //第二种情况：模式串中没有子串匹配上好后缀，但找到一个最大前缀
    int j = 0;
    for (int i = m - 2; i >= 0; i--) {
        if (suff[i] == i + 1) {
            for (; j < m - 1 - i; j++) {
                gs[j] = m - 1 - i;
            }
        }
    }
    
    //第三种情况：模式串中有子串匹配上好后缀
    for (int i = 0; i <= m - 2; i++) {
        gs[m - 1 - suff[i]] = m - 1- i;
    }
}

void BM(string &s, int &n, string &p, int &m) {
    int bc[MAX_LENGTH];
    int gs[MAX_LENGTH];
    GetBC(p, m, bc);
    GetGS(p, m, gs);
    
    int j = 0, i = 0;
    while (j <= n - m) {
        for (i = m - 1; i >= 0 && p[i] == s[i + j]; i--) {}
        if (i < 0) {
            cout << "在下标" << j << "位置找到匹配\n";
            j += gs[0];
        }
        else {
            j += max(bc[s[i + j]] - m + 1 + i, gs[i]);
        }
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    string s, p;
    int n, m;
    getline(cin, s);
    getline(cin, p);
    n = (int)s.size();
    m = (int)p.size();
    BM(s, n, p, m);
    cout << endl;
    return 0;
}

总结

坏字符比较好理解，但好后缀我花了较长的时间去调试琢磨。比如可否调整这三个情况的执行顺序（这三个情况在同一位置的计算位数：第一 > 第二 > 第三，尽量少移动避免错过完全匹配）、为何区别处理第二和第三种情况（找到真好后缀更新位置是一个区间，而好后缀的更新位置是单独一个，这是因为真好后缀的左侧没有需要匹配的字符，而好后缀则需要考虑左侧的匹配情况）、在计算过程中两种启发法则的正常情况和特殊情况怎么互相补充（好后缀的特殊情况出现在末尾第一位，而坏字符的特殊情况出现在非末尾第一位）等等问题都是比较让人疑惑的，这里就不在赘述了。总之测试数据跑起来，断点调试开起来，慢慢体会BM算法的构思精妙之处吧！

参考资料

博客

http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html
https://www.cnblogs.com/gaochundong/p/boyer_moore_string_matching_algorithm.html
https://blog.csdn.net/appleprince88/article/details/11881323

书籍

《程序员实用算法》