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

核心思想：两大规则

1. 坏字符规则（Bad Character Rule）：当发生不匹配时，根据文本中导致不匹配的字符（“坏字符”）在模式串中的位置决定滑动距离。
2. 好后缀规则（Good Suffix Rule）：利用已匹配的后缀部分（“好后缀”）在模式串中其他出现的位置来决定最大安全滑动距离。

C++实现步骤

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

1. 构建坏字符表（badCharTable）
2. 构建好后缀表（goodSuffixTable）
3. 主匹配循环，结合两个表进行跳跃

1. 构建坏字符表

void buildBadCharTable(const std::string& pattern, std::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;    }}

2. 构建好后缀表

void buildGoodSuffixTable(const std::string& pattern, std::vector<int>& goodSuffix) {    int m = pattern.length();    std::vector<int> suffix(m);        // 计算suffix数组    suffix[m - 1] = m;    for (int i = m - 2; i >= 0; --i) {        int j = i;        while (j >= 0 && pattern[j] == pattern[m - 1 - (i - j)]) {            --j;        }        suffix[i] = i - j;    }        // 初始化goodSuffix表    for (int i = 0; i < m; ++i) {        goodSuffix[i] = m;    }        // 填充goodSuffix表    int j = 0;    for (int i = m - 1; i >= 0; --i) {        if (suffix[i] == i + 1) {            for (; j < m - 1 - i; ++j) {                if (goodSuffix[j] == m) {                    goodSuffix[j] = m - 1 - i;                }            }        }    }        // 处理非前缀匹配的情况    for (int i = 0; i <= m - 2; ++i) {        goodSuffix[m - 1 - suffix[i]] = m - 1 - i;    }}

3. 主匹配函数

int boyerMooreSearch(const std::string& text, const std::string& pattern) {    int n = text.length();    int m = pattern.length();        if (m == 0) return 0;        std::vector<int> badChar(256, -1);    std::vector<int> goodSuffix(m, 0);        buildBadCharTable(pattern, badChar);    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) {            // 找到匹配            return s;        } else {            // 计算滑动距离            int badCharShift = j - badChar[static_cast<unsigned char>(text[s + j])];            int goodSuffixShift = goodSuffix[j];            s += std::max(badCharShift, goodSuffixShift);        }    }        return -1; // 未找到}

完整示例与测试

#include <iostream>#include <vector>#include <algorithm>// 此处插入上面三个函数...int main() {    std::string text = "ABAAABCDABCABC";    std::string pattern = "ABC";        int pos = boyerMooreSearch(text, pattern);        if (pos != -1) {        std::cout << "Pattern found at index: " << pos << std::endl;    } else {        std::cout << "Pattern not found." << std::endl;    }        return 0;}

总结

通过本教程，我们详细讲解了Boyer-Moore算法实现的原理与C++代码。BM算法利用坏字符和好后缀规则实现跳跃式匹配，是高效字符串搜索的经典代表。掌握它不仅能提升编程能力，还能深入理解算法设计的巧妙之处。

希望这篇面向初学者的教程能帮助你轻松入门BM算法！记得多动手实践，尝试修改模式串和文本内容，观察匹配过程的变化。