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

BM 算法详解只需这一篇文章从零开始掌握高效的字符串匹配博主主页LiUEEEEEC专栏C语言专栏数据结构专栏排序算法专栏力扣牛客经典题目专栏前言假设你有一个长度为n的文本串想在里面找一个长度为m的模式串最朴素的做法是逐位比较时间复杂度 O(nm)。当数据量一大就扛不住了。BMBoyer-Moore算法是一种能在实际场景中远快于朴素算法的字符串匹配算法。它的核心思想很反直觉从模式串的末尾开始比较并且利用两个启发式规则来尽可能多地跳过不必要的比较。目录核心思想两个关键规则坏字符规则Bad Character好后缀规则Good Suffix完整算法流程C 完整实现图解示例复杂度分析BM 与其他算法对比总结核心思想传统字符串匹配从左往右逐字符比较BM 算法的两个颠覆性特点从右往左比较模式串与文本串对齐后从模式串的最后一个字符开始往前比较。不匹配时大跳发现不匹配后不是只移动一位而是根据两个规则计算出一个较大的偏移量直接跳过去。为什么从右往左比较更好因为当末尾字符不匹配时我们可以直接跳过整个模式串的长度而不需要回头检查前面的字符。两个关键规则当模式串 P 与文本串 T 在某个位置对齐时如果发生不匹配假设在模式串的第j位不匹配BM 算法用以下两个规则分别计算偏移量然后取较大值规则名称含义规则一坏字符规则Bad Character利用文本串中那个不匹配的字符来决定跳多远规则二好后缀规则Good Suffix利用已经匹配成功的后缀来决定跳多远坏字符规则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(conststringpattern,intbc[256]){// 初始化为 -1表示该字符不在模式串中fill(bc,bc256,-1);intmpattern.size();for(inti0;im;i){bc[(unsignedchar)pattern[i]]i;// 记录最靠右的位置}}关键理解bc数组告诉我们当遇到坏字符x时模式串中最近的x在哪。偏移量 坏字符位置 - bc[坏字符]。如果bc[坏字符]为 -1不存在则直接跳过整个坏字符位置。好后缀规则Good Suffix定义假设模式串 P 与文本串 T 从右往左比较在某个位置不匹配但此时模式串的后半部分[j1, 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 数组好后缀的预处理比较复杂需要两个辅助数组suffix[]suffix[i]表示模式串中以i为结尾的后缀与模式串的某个前缀匹配的最大长度。gs[]gs[j]表示在位置j不匹配时模式串应该右移多少位。// 构建好后缀数组voidbuildGoodSuffix(conststringpattern,intgs[]){intmpattern.size();// suffix[i] 模式串中以 i 结尾的后缀与某个前缀匹配的最大长度// 即 pattern[m-len..m-1] pattern[i-len1..i]vectorintsuffix(m,-1);// 从右往左逐个位置计算for(inti0;im-1;i){intji;intk0;// 从位置 i 开始向左扩展看能匹配多长while(j0pattern[j]pattern[m-1-k]){j--;k;suffix[k]j1;// 记录匹配长度 k 对应的起始位置}}// 三种情况填充 gs 数组for(inti0;im;i){gs[i]m;// 默认值跳过整个模式串情况3}// 情况2前缀与好后缀的后缀匹配for(intim-1;i0;i--){if(suffix[i]!-1){// 好后缀长度为 i在模式串中的位置是 m-igs[m-1-i]m-1-suffix[i]1;}}// 情况1模式串中有另一个与好后缀完全相同的子串for(inti0;im-1;i){intjm-1-suffix[i];gs[j]m-1-i;}}注意好后缀的预处理代码比较复杂初学者不必一开始就完全理解每一行。建议先理解坏字符规则再回头啃好后缀规则。完整算法流程1. 预处理构建 bc[] 数组和 gs[] 数组 2. 将模式串与文本串左对齐 3. 从模式串末尾开始从右往左逐字符比较 a. 如果全部匹配 → 记录匹配位置右移 gs[0] 位继续 b. 如果不匹配 → 计算 - 坏字符偏移 j - bc[text[ij]] j 是不匹配位置i 是当前对齐位置 - 好后缀偏移 gs[j] - 取较大值作为实际偏移量 4. 重复步骤 3直到模式串右端超出文本串长度C 完整实现下面是一个可以直接运行的完整 BM 算法实现#includeiostream#includestring#includevector#includealgorithmusingnamespacestd;classBoyerMoore{private:string pattern;intm;intbc[256];// 坏字符数组vectorintgs;// 好后缀数组// 构建坏字符数组voidbuildBadChar(){fill(bc,bc256,-1);for(inti0;im;i){bc[(unsignedchar)pattern[i]]i;}}// 构建好后缀数组voidbuildGoodSuffix(){gs.resize(m,m);vectorintsuffix(m,-1);// 计算 suffix 数组for(inti0;im-1;i){intji;intk0;while(j0pattern[j]pattern[m-1-k]){j--;k;suffix[k]j1;}}// 情况2前缀匹配for(intim-1;i0;i--){if(suffix[i]!-1){gs[m-1-i]m-1-suffix[i]1;}}// 情况1完全匹配for(inti0;im-1;i){intjm-1-suffix[i];gs[j]m-1-i;}}public:BoyerMoore(conststringpat):pattern(pat),m(pat.size()){buildBadChar();buildGoodSuffix();}// 在文本串 text 中搜索所有 pattern 的出现位置vectorintsearch(conststringtext){vectorintresult;intntext.size();if(m0)returnresult;inti0;// 模式串在文本串中的对齐位置while(in-m){intjm-1;// 从模式串末尾开始比较// 从右往左比较while(j0pattern[j]text[ij]){j--;}if(j0){// 全部匹配成功result.push_back(i);igs[0];// 右移}else{// 不匹配计算偏移量intbcShiftj-bc[(unsignedchar)text[ij]];intgsShiftgs[j];imax(bcShift,gsShift);}}returnresult;}};intmain(){string textHERE IS A SIMPLE EXAMPLE;string patternEXAMPLE;BoyerMoorebm(pattern);vectorintpositionsbm.search(text);cout文本串: textendl;cout模式串: patternendl;cout匹配位置: ;for(intpos:positions){coutpos ;}coutendl;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[ ]字符ABCD其他位置3425-1例‘A’ 在模式串中最靠右的位置是下标 3‘D’ 在下标 5。第二步开始匹配对齐位置 i0T: A B C A B C A B D P: A B C A B D ↑ 从右往左比较下标 5T[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 Fbc[] 数组字符CDEF其他位置0123-1第 1 轮i0T: 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 2i 右移 2 位 → i2第 2 轮i2T: 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 → 匹配全部匹配记录位置 i2。复杂度分析时间复杂度情况复杂度说明最好情况O(n/m)每次比较都能跳过整个模式串长度最坏情况O(nm)极端情况下退化如模式串和文本串都是同一字符重复平均情况O(n/m) 到 O(n)实际使用中非常高效空间复杂度O(m σ)其中 σ 是字符集大小通常 256用于存储bc[]和gs[]数组。为什么实际很快BM 算法在实际应用中通常比 O(n) 的 KMP 算法还要快原因是坏字符规则经常能让模式串跳过很远尤其是字符集较大时如英文字母、中文等从右往左比较使得不匹配时的跳跃距离更大实际经验在英文文本搜索中BM 算法的比较次数大约只有文本长度的 20%-30%。BM 与其他算法对比算法预处理时间匹配时间最坏匹配时间平均特点朴素算法无O(nm)O(n)简单但慢KMPO(m)O(n)O(n)稳定 O(n)但实际不如 BM 快BMO(mσ)O(nm)O(n/m)实际最快工业界首选Rabin-KarpO(m)O(nm)O(n)适合多模式匹配常见问题 FAQQ1为什么 BM 算法不是 O(n) 的却比 KMP 快KMP 的最坏情况是严格的 O(n)但它的每一步只能前进 1 位。BM 算法虽然最坏是 O(nm)但在实际文本中坏字符规则经常能跳过很多位平均比较次数远少于 n 次。就像开车KMP 永远匀速 60km/hBM 可能偶尔停一下但大部分时间跑 120km/h。Q2坏字符规则和好后缀规则哪个更重要坏字符规则更重要。在大多数实际场景中坏字符规则就能提供足够的跳转距离。好后缀规则主要处理坏字符规则不足的边缘情况。实现时两个偏移量取较大值即可。Q3BM 算法适合什么场景文本编辑器的查找功能如 VS Code、Sublime Text数据库的字符串搜索生物信息学中的 DNA 序列匹配任何需要在大文本中找固定模式串的场景Q4能不能只用坏字符规则可以这就是简化版 BM 算法。在字符集较大如 ASCII/Unicode的场景下只用坏字符规则的效果已经很好了。下面是简化版实现// 简化版 BM只用坏字符规则vectorintbmSimple(conststringtext,conststringpattern){vectorintresult;intntext.size(),mpattern.size();// 构建坏字符数组intbc[256];fill(bc,bc256,-1);for(inti0;im;i){bc[(unsignedchar)pattern[i]]i;}inti0;while(in-m){intjm-1;while(j0pattern[j]text[ij]){j--;}if(j0){result.push_back(i);i;// 匹配成功右移 1 位继续找}else{imax(1,j-bc[(unsignedchar)text[ij]]);}}returnresult;}总结要点内容核心思想从右往左比较 利用不匹配信息大跳坏字符规则利用不匹配字符在模式串中的位置计算偏移好后缀规则利用已匹配后缀在模式串中的其他出现位置计算偏移偏移决策两个规则取较大值实际表现通常比 KMP 更快是工业界的首选单模式匹配算法预处理O(m σ) 构建两个数组空间O(m σ)建议学习路径先理解朴素算法O(nm)理解 KMP 的 next 数组思想回来学 BM 的坏字符规则最后攻克好后缀规则BM 算法的代码实现比 KMP 复杂一些但一旦理解了从右往左比较 大跳的思路整个逻辑其实很自然。建议把完整代码跑一遍用 debugger 单步跟踪每一轮的比较和跳转这是理解 BM 算法最快的方式。