字符串匹配 - Boyer–Moore 算法原理和实现

Boyer–Moore 算法 是用来在字符串中搜索一个子字符串的算法。

本文内容较多，需要读者静心阅读。

内容目录：

• Boyer-Moore 算法主过程
• 坏字符的办法、实现思路 和 坏字符表
• 好后缀的办法、实现思路 和 好后缀表
• 复杂度分析

问题 ¶

在长度为 n 的字符串 s 中搜索长度为 m 的子串 p 的位置。

本文以 ABCDABEABDCBCDDBBCDBACD 为主串 ，BCDBACD 为子串，作为用例。

算法过程 ¶

首先将两个字符串左对齐，对子串 p 进行 自右向左 的逐一比对。

第一次比对，即在字符 E 失配。 由于 E 不在子串 p 中，因此，可以直接把整个子串右移到其右边。

继续向前匹配，此时在下图 1.3 中的红色部分失配。

但是，失配的 B 在子串 p 中，就在当前位置靠左一位的位置。 要想子串和主串在附近匹配成功，至少字符 B 要对的齐。 为了避免错过 B 的匹配，只能找到靠的最近的 B 对齐，也就是右移一位。

继续向前匹配，在下图 1.5 中的红色部分失配。

沿用刚才上面的思路，失配的 D 也在子串中，右移 p ，让它们对齐：

总结出来规律了， 当失配的时候，右移子串，使得主串中失配的字符和子串中左边最近的相同字符对齐。如果不存在相同字符，就把整个子串右移到失配字符的右侧。

坏字符的办法 ¶

常把失配处的字符叫做「坏字符」，每次右移，就要把 坏字符和子串中最近的坏字符对齐。

Boyer–Moore 算法和 KMP 算法 的思路类似，都是在失配处动脑筋，跳过无必要的比对，以加快搜索。

按这个思路，可以继续匹配下去，直到命中。

好后缀的办法 ¶

上面坏字符的办法，还不够快。

比如下面这次对齐：

此时，已知的信息是，主串中有已经匹配好的 CD ，它同时也是子串 p 的后缀，常叫做「好后缀」。

要想子串在附近和主串匹配成功，它们的共同子串 CD 就要对的齐，所以，把对齐坏字符的办法应用到好后缀上， 找到最近的好后缀进行右移对齐。

如此一来，右移的更多了些。

好后缀的办法就是， 失配时，右移子串，使得主串中的好后缀和子串中左边最近的重复串对齐 。 同样的，如果存在好后缀，而左边没有重复串时，那么直接把 p 右移到整个好后缀右边就好了。

综合两个办法后，整个搜索过程优化为下面的样子，总体上比只用坏字符的办法，少了两步。

当存在好后缀的时候，由于其长度比坏字符要小，所以一般的，在子串的左边出现的概率相对更低。因此，优化效果更明显， 但不尽然。综合使用时采用右移距离更大的一个 。

编码思路 ¶

先考虑失配时迭代变量如何跳转的问题。

假设，主串和子串的迭代变量分别是 i 和 j 。

在失配时，显然， 子串回到尾巴，即 j → m - 1 。

关键是计算失配时 i 的迭代量。

坏字符的办法

先考虑坏字符的办法。遇到一个坏字符的时候，假设子串中左边最近的坏字符对子串尾巴的距离是 d。

从下图可以推断出主串的迭代量就是 d：

特殊地，坏字符在子串左边不存在时，主串迭代的量应是子串长度 m ，则取 d = m 来满足。

好后缀的办法

对于好后缀的办法，道理是相似的 。

把拿来对齐的左边的重复串叫做 repeat， 把对齐好后缀的过程，看作对齐 repeat 前面那个字符的过程，即可复用上面的思路。 如此一来，假设 repeat 前面字符到尾巴字符的距离是 d ，则失配的时候，主串的迭代量就是 d。

进一步地，若假设重复串 repeat 的头部的位置是 t 的话， d 其实是 m - t 。

如果重复串 repeat 在 p 的开头，前面没有字符，此时主串的迭代量是 m，而 t 恰好是 0 ，仍然满足 d = m - t 的关系。 下面的图 2.4 构造了这种情况 （为说明问题，对本文用例稍加改造）：

总而言之，好后缀的办法，分为两种情况：

1. 好后缀在左边：d = m - t
2. 好后缀不在左边：d = m + len(suffix) - len(prefix)

事实上，无论坏字符的办法、还是好后缀的办法， 失配情况下，主串的迭代量是与主串无关的 。

坏字符表 ¶

前面所说的 d 预处理成为一个表格，包括两个维度：主串中的坏字符 和 子串失配的位置，如下图所示 （问号表示其他字符）：

假设字符集的大小是 S （一般取 ASCII 表 的大小 256） 。 事实上，此表格可以用归纳的方法，以 O(S * m) 的线性时间复杂度计算得出。

其方法是， 假设当前格子对应的子串失配的字符是 p[k] ，自上而下，自左而右进行填表：

• 第一列，全部填写 m 。
• 如果「坏字符」等于 p[k-1] 的话，则填入 m - 1 - k 。
• 否则，拷贝当前格子左边格子的数值。

这个表格的空间占用则是 O(S * m) 。 实际中，大多数的编码实现都只取最后一列，即只采用一个一维表格，其具有常数大小的空间占用。 例如，Golang 官方的字符串搜索 采用 Boyer-Moore 算法，构建的是一维坏字符表。

另外，Boyer-Moore 算法 - 维基百科 中也确有指出 创建二维坏字符表的方法， 并且有给出使用二维坏字符表的 Python 实现。

采用一维坏字符表时，表格含义即退化为：坏字符在子串中最右侧出现的位置，距离尾巴字符的距离 。

同时，构建坏字符表格的方法也会更简单：

• 初始化一维表格 table 的每一项是 m 。

• 假设 p 的尾巴字符的位置是 last = m-1 ：

  对尾巴左边的每个字符 char = p[k] ，不断覆盖 table[char] = last - k 即可。

  上面注意 k = 0..(last - 1) ，尾巴字符左边的字符才有可能成为坏字符的对齐目标。

一维的坏字符表格如下所示：

// ComputeBadCharTable 计算一维坏字符表
void ComputeBadCharTable(char *p, int m, int table[]) {
    // 初始化每一个字符的坏字符表值为 m
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        table[i] = m;
    }
    // 对尾巴左边的字符，不断覆盖它到尾巴 last 的距离
    // 坏字符的对齐目标绝不在尾巴字符上。
    int last = m - 1;
    for (int i = 0; i < last; i++) {
        char ch = p[i];
        table[ch] = last - i;
    }
}

好后缀表 ¶

好后缀表的构造一般被认为是 Boyer-Moore 算法中最难的部分。

前面已经分析 好后缀方法中的 d 存在两种情况。

明确现在的问题，对于搜索串 p 的所有后缀 suffix(k) ，找出对应的 d，其中 k 是失配的位置。

假设存放 d 的一维数组是 table ，考虑此表格如何填写。

参考 前面的分析 ， 共有两种情况，分两次填表。

先处理第二种情况的填表过程，即 好后缀不在左边的情况。

好后缀不在左边的情况

为方便说明，本部分的搜索串的示例调整为 DDDBDDD 。

参考 前面的分析 ，此情况下的 d = m + len(suffix) - len(prefix) 。

举例来说，当好后缀为 BDDD 的时候，d 的求值如下图所示：

问题是：如何找到搜索串的每一个后缀的部分匹配前缀 ？

下图中，suffix(k) 表示在 k 处失配时的好后缀，黄色框表示其对应的部分匹配前缀， 右边依次列出前缀的长度：

前缀长度的变化是有规律的，从上而下填写：

• 如果后缀是一个前缀，计算 len(prefix) = len(suffix) ，并记录为 last_prefix_length 。
• 否则，沿用上一次的计算结果： len(prefix) = last_prefix_length 。

是否和 KMP 算法的 next 数组计算方式 类似呢。

len(prefix) 的计算清楚之后，此情况的填表过程即得到解决。

// ComputeGoodSuffixTableCaseNotInLeft
// 填写好后缀表，处理情况：好后缀不在搜索串的左边的情况
void ComputeGoodSuffixTableCaseNotInLeft(char *p, int m, int table[]) {
    int last_prefix_length = 0;

    // 失配位置在 m - 1 时，好后缀无意义，设为跳动最少 1
    table[m - 1] = 1;

    // i 表示后缀的起始位置
    for (int i = m - 1; i > 0; i--) {
        // k 表示失配的位置
        int k = i - 1;
        int suffix_length = m - i;
        char *suffix = p + i;
        int prefix_length = 0;

        if (strncmp(p, suffix, suffix_length) == 0) {
            // 如果后缀是一个前缀
            prefix_length = suffix_length;
            last_prefix_length = prefix_length;
        } else {
            // 否则，沿用上次结果
            prefix_length = last_prefix_length;
        }

        // 计算 d
        table[k] = m + suffix_length - prefix_length;
    }
}

好后缀在左边的情况

为方便说明，本部分的搜索串的示例调整为 DCDBCDACD 。

参考 前面的分析 ，此情况下的 d = m - t ， 如何计算 t 取决于如何找到左边最右的重复串。

引入一个概念：最长公共后缀 ，如图所示：

// GetLongestCommonSuffixLength 返回字符串 a 和 b 的最长公共后缀长度。
// 比如 'simple' 和 'example' 的最长公共后缀是 'mple' ，长度是 4.
int GetLongestCommonSuffixLength(char *a, int a_length, char *b, int b_length) {
    int i = 0;
    for (i = 0; i < a_length && i < b_length; i++) {
        if (a[a_length - 1 - i] != b[b_length - 1 - i]) {
            break;
        }
    }
    return i;
}

如果左边存在重复串，那么它是一个前缀 和 p 的最长公共后缀 。

下图中，两个前缀串和 p 的最长公共后缀相同，取长的那个。 这样才能找到 最右的 重复串。

也就是，前缀要从短往长去找，用长的去覆盖短的计算结果 。

如果前缀以 e 下标结尾， 显然 t = e + 1 - len(suffix) 。

至此，思路如下：

• 对 p 的每个前缀，计算它和 p 的最长公共后缀，设其长度 len
• 即确定了长度为 len 的后缀，相应的 t 亦可得出。
• 长的前缀的计算结果覆盖短的。

进一步的说明

为方便说明，将搜索串 p 的例子调整为 ACDBCDABCD 。

后缀 CD 对应的前缀则是：

注意的是，此情况下重复串的位置，在 prefix1 结尾。

并非巧合，重复串和好后缀左边的字符必然不同， 否则右移后坏字符仍然失配。

// ComputeGoodSuffixTableCaseInLeft
// 填写好后缀表，处理情况：好后缀在搜索串的左边的情况
void ComputeGoodSuffixTableCaseInLeft(char *p, int m, int table[]) {
    // e 表示对应的前缀的结尾位置
    for (int e = 0; e < m - 1; e++) {
        // 前缀字符串
        char *prefix = p + e;
        // 前缀的长度
        int prefix_length = e + 1;
        // 最长公共后缀的长度，即好后缀的长度
        int suffix_length =
            GetLongestCommonSuffixLength(p, m, p, prefix_length);

        if (suffix_length > 0) {
            // 好后缀长度 > 0 才有意义
            // t 是重复串的起始位置
            int t = e + 1 - suffix_length;
            // 失配字符的位置
            int k = m - 1 - suffix_length;
            // 填表，覆盖
            table[k] = m - t;
        }
    }
}

// ComputeGoodSuffixTable 计算好后缀表的方法
void ComputeGoodSuffixTable(char *p, int m, int table[]) {
    // 先处理第二种情况：好后缀在搜索串左边不存在的情况
    // 即好后缀和搜索串部分匹配或者完全不匹配的情况
    ComputeGoodSuffixTableCaseNotInLeft(p, m, table);
    // 再处理第一种情况：好后缀在搜索串左边存在的情况
    ComputeGoodSuffixTableCaseInLeft(p, m, table);
}

查找过程 ¶

可以看到，坏字符表和好后缀表只和搜索串有关，可以提前生成 。

至此，已可以完成整个 Boyer-Moore 算法：

• 对搜索串，填写坏字符表和好后缀表
• 先对齐主串和搜索串。
• 自右向左匹配。
• 失配时，挑选两张表中最大的跳转量，作为主串的迭代量。

#define max(a, b) ((a < b) ? b : a)

// BoyerMoore 从长度为 n 的字符串 s 中查找长度为 m 的字符串 p ， 返回其位置.
// 找不到则返回 -1
int BoyerMoore(char *s, int n, char *p, int m) {
    int bad_char_table[ALPHABET_SIZE];
    int good_suffix_table[m];

    ComputeBadCharTable(p, m, bad_char_table);
    ComputeGoodSuffixTable(p, m, good_suffix_table);

    // 初始化，i, j 右对齐
    int i = m - 1;

    while (i < n) {
        int j = m - 1;

        // 自右向左匹配
        while (j >= 0 && p[j] == s[i]) {
            j--;
            i--;
        }

        if (j < 0) {
            // 命中, 返回起始位置
            return i + 1;
        }

        // 失配时，跳转的多少，选取坏字符表和好后缀表中最大的跳转量
        i += max(bad_char_table[s[i]], good_suffix_table[j]);
    }

    return -1;
}

此外，Go 语言的实现可以参考官方的 search.go 。

复杂度分析 ¶

一维坏字符表构建的时间复杂度是常数的 O(S + m) ，其中 S 是所考虑的字符集的大小。 二维坏字符表构建的时间复杂度则是 O(S * m) ，均是 m 相关的线性时间复杂度。

好后缀表在两种情况下的构建的时间复杂度均为 O(m^2) ，不过一般情况下搜索串的长度相对主串会很小， Golang 的官方实现 对好后缀表的构建方法亦和本文的一致。

事实上， Boyer-Moore 算法 - 维基百科 告诉我们，好后缀表可以在线性时间内构建，可以参考其给出的 Python 实现 ， 其中采用的是 Z-算法。

查找过程的时间复杂度是 O(m * n) ，其中最好情形如下图所示，时间复杂度是 O(n / m) ：

最坏情形的时间复杂度是 O(m * n) ，退化成为简易的二次循环匹配：

结语 ¶

Boyer-Moore 的坏字符办法和好后缀办法，可以综合使用，也可以单独使用一种，其中坏字符的办法实现更简单一些。

事实上，我认为 Boyer-Moore 算法远不如 KMP 算法 干练精巧，其主体查找过程虽然更容易理解，但是两种表格的计算，尤其是好后缀表的构建， 确是相对复杂的。

相关阅读：

• 字符串匹配 - KMP 算法
• boyer-moore C 实现完整代码

（完）