Boyer-Moore算法通过坏字符和好后缀规则从模式串末尾开始匹配，利用预处理跳转表跳过不必要的比较，在C++中通过badchar数组和good_suffix数组实现，主函数结合两者取最大偏移量进行滑动，高效适用于长模式串匹配。
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 suffix(m);// 计算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 = 0 && pattern[g] == pattern[g + m - 1 - f]) --g; suffix[i] = f - g; }}// 初始化good_suffix数组for (int i = 0; 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 boyer_moore_search(const string& text, const string& pattern) { int n = text.length(); int m = pattern.length(); vector matches;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 = 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 #include #include using namespace std;int main() {string text = "ABAAABCD";string pattern = "ABC";vector 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算法实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1478596.html
微信扫一扫 
支付宝扫一扫 
