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 < 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 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 <= 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
#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文本时需调整查表方式。不复杂但容易忽略边界条件。
