BM算法详解（C++语言实现高效字符串匹配）

C++实现BM算法步骤

我们将分三步实现BM算法：

1. 构建坏字符表（bad character table）
2. 构建好后缀表（good suffix table）
3. 主匹配函数，结合两个表进行高效搜索

完整C++代码实现

以下是完整的Boyer-Moore算法实现代码，包含详细注释，适合初学者理解：

#include <iostream>#include <vector>#include <algorithm>using namespace std;// 构建坏字符表void buildBadCharTable(const string& pattern, vector<int>& badChar) {    int m = pattern.length();    for (int i = 0; i < 256; ++i)        badChar[i] = -1;    for (int i = 0; i < m; ++i)        badChar[static_cast<unsigned char>(pattern[i])] = i;}// 构建好后缀表void buildGoodSuffixTable(const string& pattern, vector<int>& goodSuffix) {    int m = pattern.length();    vector<int> suffix(m, 0);    // 计算suffix数组    suffix[m - 1] = m;    int g = m - 1;    for (int i = m - 2; i >= 0; --i) {        if (i > g && suffix[i + m - 1 - (m - 1 - g)] < i - g)            suffix[i] = suffix[i + m - 1 - (m - 1 - g)];        else {            if (i < g) g = i;            while (g >= 0 && pattern[g] == pattern[g + m - 1 - i])                g--;            suffix[i] = i - g;        }    }    // 初始化goodSuffix表    for (int i = 0; i < m; ++i)        goodSuffix[i] = m;    // 应用suffix数组填充goodSuffix    int j = 0;    for (int i = m - 1; i >= -1; --i) {        if (i == -1 || suffix[i] == i + 1) {            while (j < m - 1 - i) {                if (goodSuffix[j] == m)                    goodSuffix[j] = m - 1 - i;                j++;            }        }    }    // 处理其他情况    for (int i = 0; i <= m - 2; ++i)        goodSuffix[m - 1 - suffix[i]] = m - 1 - i;}// BM算法主函数int boyerMooreSearch(const string& text, const string& pattern) {    int n = text.length();    int m = pattern.length();    if (m == 0) return 0;    vector<int> badChar(256, -1);    buildBadCharTable(pattern, badChar);    vector<int> goodSuffix(m, 0);    buildGoodSuffixTable(pattern, goodSuffix);    int s = 0; // 模式串相对于文本的偏移量    while (s <= n - m) {        int j = m - 1;        while (j >= 0 && pattern[j] == text[s + j])            j--;        if (j < 0) {            cout << "Pattern found at index " << s << endl;            s += (s + m < n) ? m - badChar[static_cast<unsigned char>(text[s + m])] : 1;        } else {            int badCharShift = j - badChar[static_cast<unsigned char>(text[s + j])];            int goodSuffixShift = goodSuffix[j];            s += max(badCharShift, goodSuffixShift);        }    }    return -1;}int main() {    string text = "ABAAABCDABCABC";    string pattern = "ABC";    boyerMooreSearch(text, pattern);    return 0;}

代码说明

上述代码实现了完整的BM算法：

• buildBadCharTable 函数为每个可能的字符（0~255）记录其在模式串中最右侧出现的位置。
• buildGoodSuffixTable 函数较为复杂，用于预处理好后缀信息。
• boyerMooreSearch 是主函数，在每次不匹配时取坏字符和好后缀两种移动方式的最大值，确保不会漏掉匹配位置。

为什么BM算法更快？

BM算法的时间复杂度在最好情况下可达 O(n/m)，其中 n 是文本长度，m 是模式长度。这意味着它在实际应用中往往比 KMP 或朴素匹配快得多，尤其当模式串较长时。这也是它成为许多工业级字符串搜索库（如 GNU grep）核心算法的原因。

总结

通过本教程，你已经掌握了BM算法的核心思想和C++字符串匹配的具体实现。无论是学习算法原理还是提升编程能力，理解Boyer-Moore算法实现都是一个重要的里程碑。记住，实践是掌握算法的关键——尝试修改代码、测试不同输入，你会对高效字符串搜索有更深的理解！