c++中如何实现Boyer-Moore算法_c++ Boyer-Moore算法实现-C++-PHP中文网

c++中如何实现Boyer-Moore算法_c++ Boyer-Moore算法实现

穿越時空

发布： 2025-10-12 08:58:01

原创

984人浏览过

Boyer-Moore算法通过坏字符和好后缀规则从模式串末尾开始匹配，利用预处理跳转表跳过不必要的比较，在C++中通过badchar数组和good_suffix数组实现，主函数结合两者取最大偏移量进行滑动，高效适用于长模式串匹配。

c++中如何实现boyer-moore算法_c++ boyer-moore算法实现

Boyer-Moore算法是一种高效的字符串匹配算法，核心思想是从模式串的末尾开始比较，利用“坏字符”和“好后缀”两个启发规则跳过尽可能多的不必要比较。在C++中实现该算法需要预处理两个规则对应的跳转表。

坏字符规则（Bad Character Rule）

当发现不匹配字符时，根据文本中当前字符在模式串中的位置决定向右移动的距离。

说明： - 对于模式串中的每个字符，记录其最靠右的位置。 - 若当前字符不在模式串中，则整个模式串可以跳过该字符。

实现方式：

使用一个数组或map存储每个字符在模式串中最后一次出现的索引。
匹配失败时，根据文本当前字符查找其在模式串中的位置，计算偏移量。

示例代码片段：

立即学习“C++免费学习笔记（深入）”；

void preprocess_bad_char(const string& pattern, int badchar[256]) {
    int m = pattern.length();
    for (int i = 0; i < 256; i++) {
        badchar[i] = -1;
    }
    for (int i = 0; i < m; i++) {
        badchar[(unsigned char)pattern[i]] = i;
    }
}

登录后复制

好后缀规则（Good Suffix Rule）

当部分匹配发生在模式串末尾时，利用已匹配的后缀信息来决定移动距离。

算家云

高效、便捷的人工智能算力服务平台

查看详情

说明： - 预处理模式串，构建一个数组，表示每个可能的好后缀对应的最小安全移动步数。 - 分三种情况：完全匹配后缀、存在匹配子串、无匹配但有前缀可接续。

实现方式：

先计算suffix数组，表示从位置i到结尾与模式串末尾最长公共后缀长度。
再基于suffix数组构建good_suffix数组。

简化版实现（常用近似）：

void preprocess_good_suffix(const string& pattern, int* good_suffix) {
    int m = pattern.length();
    vector<int> suffix(m);
<pre class="brush:php;toolbar:false;"><pre class="brush:php;toolbar:false;">// 计算suffix数组
suffix[m - 1] = m;
int g = m - 1, f;
for (int i = m - 2; i >= 0; --i) {
    if (i > g && suffix[i + m - 1 - f] < i - g)
        suffix[i] = suffix[i + m - 1 - f];
    else {
        if (i < g) g = i;
        f = i;
        while (g >= 0 && pattern[g] == pattern[g + m - 1 - f])
            --g;
        suffix[i] = f - g;
    }
}

// 初始化good_suffix数组
for (int i = 0; i < m; i++)
    good_suffix[i] = m;

// 根据suffix填充good_suffix
for (int i = m - 1; i >= 0; i--) {
    if (suffix[i] == i + 1) {
        for (int j = 0; j < m - 1 - i; j++) {
            if (good_suffix[j] == m)
                good_suffix[j] = m - 1 - i;
        }
    }
}
for (int i = 0; i <= m - 2; i++) {
    good_suffix[m - 1 - suffix[i]] = m - 1 - i;
}

登录后复制

}

主匹配函数

结合两个规则，在每次失配时选择最大跳跃距离进行滑动。

vector<int> boyer_moore_search(const string& text, const string& pattern) {
    int n = text.length();
    int m = pattern.length();
    vector<int> matches;
<pre class="brush:php;toolbar:false;"><pre class="brush:php;toolbar:false;">if (m == 0) return matches;

int badchar[256];
preprocess_bad_char(pattern, badchar);

int* good_suffix = new int[m];
preprocess_good_suffix(pattern, good_suffix);

int s = 0;
while (s <= n - m) {
    int j = m - 1;
    while (j >= 0 && pattern[j] == text[s + j])
        j--;

    if (j < 0) {
        matches.push_back(s);
        s += (s + m < n) ? m - good_suffix[0] : 1;
    } else {
        int bc_shift = j - badchar[(unsigned char)text[s + j]];
        int gs_shift = good_suffix[j];
        s += max(bc_shift, gs_shift);
    }
}

delete[] good_suffix;
return matches;

登录后复制

}

使用示例

完整调用示例：

#include <iostream>
#include <vector>
#include <string>
using namespace std;
<p>int main() {
string text = "ABAAABCD";
string pattern = "ABC";
vector<int> result = boyer_moore_search(text, pattern);
for (int pos : result) {
cout << "Match found at index " << pos << endl;
}
return 0;
}

登录后复制

基本上就这些。理解两个规则的核心逻辑是关键，实际应用中可以根据需求简化好后缀处理。虽然实现略复杂，但匹配阶段效率很高，特别适合长模式串场景。注意字符编码问题，尤其是非ASCII文本时需调整查表方式。不复杂但容易忽略边界条件。

以上就是c++++中如何实现Boyer-Moore算法_c++ Boyer-Moore算法实现的详细内容，更多请关注php中文网其它相关文章！