BM 算法详解：只需这一篇文章，从零开始掌握高效的字符串匹配

BM 算法详解：只需这一篇文章，从零开始掌握高效的字符串匹配

博主主页：LiUEEEEE
C++专栏
C语言专栏
数据结构专栏
排序算法专栏
力扣牛客经典题目专栏

前言

假设你有一个长度为n的文本串，想在里面找一个长度为m的模式串，最朴素的做法是逐位比较，时间复杂度 O(nm)。当数据量一大就扛不住了。

BM（Boyer-Moore）算法是一种能在实际场景中远快于朴素算法的字符串匹配算法。它的核心思想很反直觉：从模式串的末尾开始比较，并且利用两个启发式规则来尽可能多地跳过不必要的比较。

目录

1. 核心思想
2. 两个关键规则
3. 坏字符规则（Bad Character）
4. 好后缀规则（Good Suffix）
5. 完整算法流程
6. C++ 完整实现
7. 图解示例
8. 复杂度分析
9. BM 与其他算法对比
10. 总结

核心思想

传统字符串匹配从左往右逐字符比较，BM 算法的两个颠覆性特点：

1. 从右往左比较：模式串与文本串对齐后，从模式串的最后一个字符开始往前比较。
2. 不匹配时大跳：发现不匹配后，不是只移动一位，而是根据两个规则计算出一个较大的偏移量，直接跳过去。

为什么从右往左比较更好？因为当末尾字符不匹配时，我们可以直接跳过整个模式串的长度，而不需要回头检查前面的字符。

两个关键规则

当模式串 P 与文本串 T 在某个位置对齐时，如果发生不匹配（假设在模式串的第j位不匹配），BM 算法用以下两个规则分别计算偏移量，然后取较大值：

坏字符规则（Bad Character）

定义

在从右往左比较的过程中，如果某个位置发现文本串的字符x与模式串的字符不匹配，那么x就是坏字符。

计算偏移

• 如果坏字符x在模式串中存在，就将模式串滑动到使得模式串中最靠右的x与文本串中的x对齐的位置。
• 如果坏字符x在模式串中不存在，就直接将整个模式串滑过坏字符的位置。

举例

文本串 T: ABCABCABD 模式串 P: ABCABD

假设我们在位置对齐时，从右往左比较到 P 的第 3 个字符（下标 2，字符 ‘C’）时发现不匹配，文本串对应位置的字符是 ‘B’（坏字符）。

模式串中 ‘B’ 最靠右出现在下标 1 的位置。所以我们把模式串右移，让模式串下标 1 的 ‘B’ 对齐文本串的坏字符 ‘B’：

移动前： ABCABCABD ABCABD ^ 坏字符位置（下标4的'B' vs 下标2的'C'） 移动后： ABCABCABD ABCABD

预处理：构建 bc 数组

我们需要一个数组bc[256]，记录每个字符在模式串中最靠右的出现位置。如果字符不存在，记为 -1。

// 构建坏字符数组voidbuildBadChar(conststring&pattern,intbc[256]){// 初始化为 -1，表示该字符不在模式串中fill(bc,bc+256,-1);intm=pattern.size();for(inti=0;i<m;i++){bc[(unsignedchar)pattern[i]]=i;// 记录最靠右的位置}}

关键理解：bc数组告诉我们，当遇到坏字符x时，模式串中最近的x在哪。偏移量 =坏字符位置 - bc[坏字符]。如果bc[坏字符]为 -1（不存在），则直接跳过整个坏字符位置。

好后缀规则（Good Suffix）

定义

假设模式串 P 与文本串 T 从右往左比较，在某个位置不匹配，但此时模式串的后半部分[j+1, m-1]已经与文本串匹配成功了，这部分就叫好后缀。

计算偏移

好后缀规则有三种情况：

情况 1：模式串中前面还有另一个与好后缀完全相同的子串，就把模式串滑到那个子串与文本串对齐的位置。

情况 2：模式串中没有另一个与好后缀完全相同的子串，但是模式串的前缀与好后缀的某个后缀匹配，就滑到前缀对齐的位置。

情况 3：以上两种都不满足，直接滑过好后缀的长度。

举例

模式串 P: A B C A B C 0 1 2 3 4 5

假设在下标 2（字符 ‘C’）处不匹配，好后缀是 “ABC”（下标 3-5）。

往前找，下标 0-2 也是 “ABC”，所以我们可以把模式串右移 3 位，让前面的 “ABC” 与文本串对齐。

预处理：构建 gs 数组

好后缀的预处理比较复杂，需要两个辅助数组：

1. suffix[]：suffix[i]表示模式串中以i为结尾的后缀，与模式串的某个前缀匹配的最大长度。
2. gs[]：gs[j]表示在位置j不匹配时，模式串应该右移多少位。

// 构建好后缀数组voidbuildGoodSuffix(conststring&pattern,intgs[]){intm=pattern.size();// suffix[i] = 模式串中以 i 结尾的后缀与某个前缀匹配的最大长度// 即 pattern[m-len..m-1] == pattern[i-len+1..i]vector<int>suffix(m,-1);// 从右往左，逐个位置计算for(inti=0;i<m-1;i++){intj=i;intk=0;// 从位置 i 开始向左扩展，看能匹配多长while(j>=0&&pattern[j]==pattern[m-1-k]){j--;k++;suffix[k]=j+1;// 记录匹配长度 k 对应的起始位置}}// 三种情况填充 gs 数组for(inti=0;i<m;i++){gs[i]=m;// 默认值：跳过整个模式串（情况3）}// 情况2：前缀与好后缀的后缀匹配for(inti=m-1;i>=0;i--){if(suffix[i]!=-1){// 好后缀长度为 i，在模式串中的位置是 m-igs[m-1-i]=m-1-suffix[i]+1;}}// 情况1：模式串中有另一个与好后缀完全相同的子串for(inti=0;i<m-1;i++){intj=m-1-suffix[i];gs[j]=m-1-i;}}

注意：好后缀的预处理代码比较复杂，初学者不必一开始就完全理解每一行。建议先理解坏字符规则，再回头啃好后缀规则。

完整算法流程

1. 预处理：构建 bc[] 数组和 gs[] 数组 2. 将模式串与文本串左对齐 3. 从模式串末尾开始，从右往左逐字符比较： a. 如果全部匹配 → 记录匹配位置，右移 gs[0] 位，继续 b. 如果不匹配 → 计算： - 坏字符偏移 = j - bc[text[i+j]] （j 是不匹配位置，i 是当前对齐位置） - 好后缀偏移 = gs[j] - 取较大值作为实际偏移量 4. 重复步骤 3，直到模式串右端超出文本串长度

C++ 完整实现

下面是一个可以直接运行的完整 BM 算法实现：

#include<iostream>#include<string>#include<vector>#include<algorithm>usingnamespacestd;classBoyerMoore{private:string pattern;intm;intbc[256];// 坏字符数组vector<int>gs;// 好后缀数组// 构建坏字符数组voidbuildBadChar(){fill(bc,bc+256,-1);for(inti=0;i<m;i++){bc[(unsignedchar)pattern[i]]=i;}}// 构建好后缀数组voidbuildGoodSuffix(){gs.resize(m,m);vector<int>suffix(m,-1);// 计算 suffix 数组for(inti=0;i<m-1;i++){intj=i;intk=0;while(j>=0&&pattern[j]==pattern[m-1-k]){j--;k++;suffix[k]=j+1;}}// 情况2：前缀匹配for(inti=m-1;i>=0;i--){if(suffix[i]!=-1){gs[m-1-i]=m-1-suffix[i]+1;}}// 情况1：完全匹配for(inti=0;i<m-1;i++){intj=m-1-suffix[i];gs[j]=m-1-i;}}public:BoyerMoore(conststring&pat):pattern(pat),m(pat.size()){buildBadChar();buildGoodSuffix();}// 在文本串 text 中搜索所有 pattern 的出现位置vector<int>search(conststring&text){vector<int>result;intn=text.size();if(m==0)returnresult;inti=0;// 模式串在文本串中的对齐位置while(i<=n-m){intj=m-1;// 从模式串末尾开始比较// 从右往左比较while(j>=0&&pattern[j]==text[i+j]){j--;}if(j<0){// 全部匹配成功result.push_back(i);i+=gs[0];// 右移}else{// 不匹配，计算偏移量intbcShift=j-bc[(unsignedchar)text[i+j]];intgsShift=gs[j];i+=max(bcShift,gsShift);}}returnresult;}};intmain(){string text="HERE IS A SIMPLE EXAMPLE";string pattern="EXAMPLE";BoyerMoorebm(pattern);vector<int>positions=bm.search(text);cout<<"文本串: "<<text<<endl;cout<<"模式串: "<<pattern<<endl;cout<<"匹配位置: ";for(intpos:positions){cout<<pos<<" ";}cout<<endl;return0;}

输出：

文本串: HERE IS A SIMPLE EXAMPLE 模式串: EXAMPLE 匹配位置: 17

示例

我们用一个完整的例子，逐步演示 BM 算法的执行过程。

场景

文本串 T: A B C A B C A B D 模式串 P: A B C A B D

第一步：预处理

坏字符数组 bc[ ]：

例：‘A’ 在模式串中最靠右的位置是下标 3；‘D’ 在下标 5。

第二步：开始匹配

对齐位置 i=0：

T: A B C A B C A B D P: A B C A B D ↑ 从右往左比较

• 下标 5：T[5]=‘C’ vs P[5]=‘D’ → 不匹配！
• 坏字符 = ‘C’，bc[‘C’] = 2
• 坏字符偏移 = 5 - 2 = 3
• 好后缀偏移 = gs[5]（此处无好后缀，为默认值 6）
• 实际偏移 = max(3, 6) = 6？不对，让我重新看——

等一下，这里我们需要更仔细地分析。因为下标 5 是从右往左比较时第一个不匹配的位置，所以此时没有好后缀（好后缀为空），gs[5] 就是默认值（即整个模式串长度）。

不过让我简化一下，用一个更直观的例子重新走一遍。

简化示例（重点展示坏字符规则）

文本串 T: B B C D E F G 模式串 P: C D E F

bc[] 数组：

第 1 轮：i=0

T: B B C D E F G P: C D E F ↑ 下标3: T[3]='D' vs P[3]='F' → 不匹配

• 坏字符 = ‘D’，bc[‘D’] = 1
• 坏字符偏移 = 3 - 1 = 2
• i 右移 2 位 → i=2

第 2 轮：i=2

T: B B C D E F G P: C D E F ↑ 下标3: T[5]='F' vs P[3]='F' → 匹配 ↑ 下标2: T[4]='E' vs P[2]='E' → 匹配 ↑ 下标1: T[3]='D' vs P[1]='D' → 匹配 ↑ 下标0: T[2]='C' vs P[0]='C' → 匹配！

• 全部匹配！记录位置 i=2。

复杂度分析

时间复杂度

空间复杂度

• O(m + σ)，其中 σ 是字符集大小（通常 256），用于存储bc[]和gs[]数组。

为什么实际很快？

BM 算法在实际应用中通常比 O(n) 的 KMP 算法还要快，原因是：

• 坏字符规则经常能让模式串跳过很远（尤其是字符集较大时，如英文字母、中文等）
• 从右往左比较使得不匹配时的跳跃距离更大

实际经验：在英文文本搜索中，BM 算法的比较次数大约只有文本长度的 20%-30%。

BM 与其他算法对比

常见问题 FAQ

Q1：为什么 BM 算法不是 O(n) 的，却比 KMP 快？

KMP 的最坏情况是严格的 O(n)，但它的每一步只能前进 1 位。BM 算法虽然最坏是 O(nm)，但在实际文本中，坏字符规则经常能跳过很多位，平均比较次数远少于 n 次。就像开车，KMP 永远匀速 60km/h，BM 可能偶尔停一下但大部分时间跑 120km/h。

Q2：坏字符规则和好后缀规则哪个更重要？

坏字符规则更重要。在大多数实际场景中，坏字符规则就能提供足够的跳转距离。好后缀规则主要处理坏字符规则不足的边缘情况。实现时，两个偏移量取较大值即可。

Q3：BM 算法适合什么场景？

• 文本编辑器的"查找"功能（如 VS Code、Sublime Text）
• 数据库的字符串搜索
• 生物信息学中的 DNA 序列匹配
• 任何需要在大文本中找固定模式串的场景

Q4：能不能只用坏字符规则？

可以，这就是简化版 BM 算法。在字符集较大（如 ASCII/Unicode）的场景下，只用坏字符规则的效果已经很好了。下面是简化版实现：

// 简化版 BM：只用坏字符规则vector<int>bmSimple(conststring&text,conststring&pattern){vector<int>result;intn=text.size(),m=pattern.size();// 构建坏字符数组intbc[256];fill(bc,bc+256,-1);for(inti=0;i<m;i++){bc[(unsignedchar)pattern[i]]=i;}inti=0;while(i<=n-m){intj=m-1;while(j>=0&&pattern[j]==text[i+j]){j--;}if(j<0){result.push_back(i);i++;// 匹配成功，右移 1 位继续找}else{i+=max(1,j-bc[(unsignedchar)text[i+j]]);}}returnresult;}

总结

建议学习路径：

1. 先理解朴素算法（O(nm)）
2. 理解 KMP 的 next 数组思想
3. 回来学 BM 的坏字符规则
4. 最后攻克好后缀规则

BM 算法的代码实现比 KMP 复杂一些，但一旦理解了"从右往左比较 + 大跳"的思路，整个逻辑其实很自然。建议把完整代码跑一遍，用 debugger 单步跟踪每一轮的比较和跳转，这是理解 BM 算法最快的方式。