1. 字符串匹配的痛点为什么大家都在找更好的查找算法1.1 暴力匹配的尴尬处境干了这么多年开发几乎没人没写过字符串查找。从文本编辑器里按CtrlF到日志系统里过滤关键字再到代码仓库里的全文检索字符串匹配无处不在。最常见、最容易想到的写法就是暴力匹配拿模式串从文本的第一个位置开始一个一个字符对齐比较如果不匹配就整体右移一位重新比较。这个思路简单到不能再简单但问题是它太慢了。假设文本长度是n模式串长度是m暴力匹配在最坏情况下的时间复杂度是O(nm)。什么意思呢比如你要在一段100MB的日志文件里反复查找某个关键词或是在一个几万行代码的项目里做全局搜索暴力匹配会让CPU白白浪费大量时间在无意义的重复比较上。举一个极端点的例子文本是AAAAAAAAAAAAAAAAAAAAB模式串是AAAAB暴力匹配会怎么做它从第一个A开始比比到第4个A发现模式串的B和文本的A不相等于是右移一位再比。这样每一个位置都要比4次才能发现不匹配一整个文本跑下来比较次数逼近nm。很多人可能觉得现代CPU这么快多比几次也无所谓。但问题是字符串匹配往往是高频率操作实时日志告警每一秒可能要匹配几千条数据在线搜索每毫秒要处理几十次用户输入。在这个场景下O(n*m)的代价完全不可接受。于是从20世纪70年代开始计算机科学家们就在想一件事能不能通过某种预处理让匹配过程跳过尽可能多的位置而不是每次都老老实实挪一格1.2 BM算法解决了什么从右向左的降维打击1977年Robert S. Boyer和J Strother Moore提出了Boyer-Moore算法也就是现在大家口中的BM算法。它的核心颠覆性在于匹配方向是反着的——从模式串的末尾开始往前比较而不是从左往右比。光这个改动还不够真正厉害的是它配套的两条移动规则——坏字符规则Bad Character Rule和好后缀规则Good Suffix Rule。靠着这两条规则BM算法在绝大多数实际文本场景下能做到亚线性级别的平均复杂度也就是说它甚至不需要看每一个字符就能完成匹配。这么说可能不太好理解我来打个比方。你在一个很长的文档里找Boyer-Moore这个词如果你的习惯从左往右一个字一个字读发现不对再往后挪一个位置那效率极低。但如果你先看文档某一段的最后一个字母是不是e模式串末尾不是而且这个字母在模式串里压根没出现过那你完全可以一次性把整段跳过去。这就是BM算法的核心直觉用末尾字符的失配信息换取大幅度的跳跃。当时写下这篇论文时作者们可能也没想到四十多年后它依然是实际工程中使用最广泛的字符串匹配算法之一。GNU grep的早期版本、文本编辑器的查找功能、基因序列比对工具、敏感词过滤系统都有它的身影。很多人在学习数据结构时可能会跳过它觉得有KMP就够了。但实际情况恰恰相反KMP在理论上很优雅最坏情况O(nm)可它的平均表现并不如BM尤其是在模式串较长、字符集较大的场景里BM要快得多。1.3 这篇文章适合谁读能收获什么不管你是刚开始学算法的在校学生还是工作几年但一直没机会啃掉这个硬骨头的工程师这篇文章都能帮到你。我会先从原理讲起用未必严谨但足够直观的方式拆解坏字符规则和好后缀规则然后给出一个可以直接运行的实现最后补上我在实际调试中踩过的坑以及BM算法在真实工程中的变体和选型建议。读完这篇文章你会彻底搞明白BM算法为什么快、什么时候用、怎么把它写对。2. 核心原理拆解坏字符规则与好后缀规则2.1 两次关键观察为什么从右往左扫更聪明先问一个问题暴力匹配失败后模式串一次只能往右挪一格挪动信息只来自不匹配位置的那个字符。这非常浪费因为失配时你手里其实握着两个信息一个是不匹配的字符长什么样另一个是模式串末尾已经成功匹配的那一段是什么模样。这两条信息都可以用来推导模式串最少要往右挪多远才能有机会匹配上。BM算法的第一个决定就是从右往左比较模式串和文本。很多初学者不理解为什么方向这么重要。想象一下你在匹配一个长模式串比如模式串长度是20。如果从左往右比前5个字符都对了第6个字符失配你得到的有效信息只有前5个字符和模式串前5个字符相同但如果从右往左比一旦最后一位就不匹配你立刻就知道了模式串的最后一个字符在文本当前位置对不上还知道那个位置上的文本字符是什么。这个信息的含金量完全不同。从右往左失配得越早你能利用的文本信息就越多跳跃距离就能越大。BM算法的整体流程大概是这样的将模式串与文本对齐在某个起始位置。从模式串的最后一个字符开始向左逐一与文本对应位置比较。如果全部匹配成功则找到一个命中位置。如果遇到某个位置失配就调用坏字符规则和好后缀规则分别计算移动距离取大者作为实际的移动距离。重复步骤2到4直到模式串超出文本范围。2.2 坏字符规则不匹配的字符就是最大的线索坏字符规则的思路特别简单。在从右往左比较的过程中你发现在某个位置模式串的字符是X而文本中对应位置的字符是YX不等于Y。此时文本里的那个字符Y就是坏字符。你的任务是根据Y在模式串中的出现情况来决定移动距离。分两种情况讨论情况一坏字符Y在模式串中出现过。这时候你希望把模式串里最后一次出现的Y挪到和文本中的Y对齐。这样Y才有机会参与匹配。移动距离等于坏字符在模式串中对应的位置减去该字符在模式串中最后一次出现的位置。如果这个距离小于等于0就退化为至少移动1位否则会倒着走。情况二坏字符Y在模式串中完全不存在。这说明模式串的任何位置都不可能是Y那把模式串整体挪到Y后面一位就好了移动距离就是当前失配位置1相当于直接跳过了整个已比较区域。这里要特别说明一个细节很多人第一次学BM算法会误以为应该记录模式串中某个字符第一次出现的位置。但实际操作恰恰相反必须记录最后一次出现的位置。为什么因为如果记录的是第一次出现的位置移动距离可能过大反而把可能存在的匹配位置跳过。举个实际案例模式串是abcabc文本字符Y是aa在模式串中出现的位置有0和3。如果记录第一次出现位置0那么从当前失配位置5开始算移动距离是5可能直接错过位置3那里的匹配机会如果记录最后一次出现位置3移动距离是2虽然移动少了点但不会漏过潜在匹配。坏字符规则的哲学就四个字宁可少跳不可跳过。2.3 好后缀规则已经配上的部分也不能浪费每当你在匹配过程中从右往左已经成功匹配了长度k的后缀然后又发现下一个字符失配这段长度为k的好后缀就是宝贵的线索。好后缀规则要解决的问题是这段已经配上的后缀会不会在模式串更靠前的位置再次出现如果会就把那段挪过来对齐如果不会那能不能用到模式串的前缀具体来说有三种情况需要处理第一种情况好后缀在模式串中靠前的位置又完整出现了一次。这个时候直接把模式串往右移让这个重复出现的子串和文本中的好后缀对齐即可。移动距离等于好后缀末尾在模式串中的位置减去该重复子串末尾在模式串中的位置。第二种情况模式串不存在与好后缀完全相同的子串但存在某个前缀恰好等于好后缀的某个后缀。举个直观的例子模式串是ababa好后缀是aba。你发现完整的好后缀aba没有在更靠前的位置再次出现但模式串的前缀aba恰好和好后缀的中间开始部分一致。这时候就可以移动模式串让这个前缀去对接文本中的好后缀部分因为这样至少可以保住已经配到的信息。第三种情况好后缀既没有在模式串中重复出现也没有任何前缀能和好后缀的后缀匹配。说明模式串无论如何都不可能在这个位置匹配直接跳过整个模式串的长度。很多教材把好后缀规则写得特别复杂但核心其实就是一句话尽可能利用已经匹配的信息寻找模式串中与好后缀部分重叠的位置并对齐它们。它的本质和KMP算法里next数组的最长公共前后缀思想是相通的只不过KMP是从左向右匹配所以用前缀BM从右向左匹配所以用后缀。2.4 两条规则怎么配合取最大值而不是简单地加法不少初学者会问既然有两条规则为什么不把两个移动距离加起来跳得不是更快吗答案是不行因为两条规则的条件依赖不同的假设把它们相加可能会把模式串移到某个后面永远不可能匹配的位置导致漏掉正确结果。正确的做法是取两者的最大值。你可能会觉得既然如此只用其中一条行不行从正确性上说单独用坏字符规则的工具叫BMH算法Horspool变体单独用好后缀规则的算法也有它们也都是正确的。但两条规则联合使用效果最好因为坏字符规则在字符集大、模式串字符重复率低的时候特别有效好后缀规则在模式串自身重复结构多的时候发挥作用。二者恰好互补所以取最大值既能保证正确性又能让跳跃距离尽可能大。这里直接给出移动距离的公式shift_bad bad_char的移动距离 shift_good good_suffix的移动距离 实际移动距离 max(shift_bad, shift_good)如果两个距离计算结果都小于等于0则统一移动1位防止死循环。3. 预处理坏字符表与好后缀表的构建方法3.1 坏字符表的构建一个数组搞定坏字符表本质上是一个哈希表key是字符value是该字符在模式串中最后一次出现的位置。由于实际场景中字符集通常是有限的比如ASCII是256个字符最简单高效的做法是直接用定长数组。构建逻辑非常简单初始化长度为256的数组bc[]全部赋值为-1 for i in range(len(pattern)): bc[pattern[i]] i就这么三行代码。注意一个细节这里变量i遍历的是整个模式串最后一次循环结束时bc里保存的位置就是每个字符最后一次出现的索引。整个过程时间复杂度O(m)空间复杂度固定O(256)。如果你处理的是Unicode文本比如中文日志那就不能用256大小的数组了。这时候可以用Python的字典dict来存坏字符表或者用哈希表原理一样。实际工程中直接拿一个256数组配合字节流处理就行因为中文一般先按UTF-8编码成字节再逐字节匹配。但如果你是直接操作字符串建议用字典。3.2 好后缀表的构建理解公共前后缀是关键好后缀表的构建比坏字符表复杂很多。经典实现思路分两步走先计算suffix数组再根据suffix数组推导移动距离表。suffix数组到底存什么定义suffix[i]的值为在模式串中从位置i开始往前的子串与模式串的后缀能够匹配的最大长度。说白了就是以位置i结尾的后缀和整个模式串的后缀有多少是重合的。举个例子模式串abcabcsuffix[2]等于什么看从位置2往前数字符是abc与模式串的后缀abc完全一致所以suffix[2]3。这个数组就是好后缀匹配情况的原始记录。怎么高效计算suffix数组有一种简单的双重循环写法def build_suffix(pattern): m len(pattern) suffix [0] * m for i in range(m - 1, -1, -1): # 从位置i往前延伸和模式串后缀比较 length 0 j i k m - 1 while j 0 and pattern[j] pattern[k]: j - 1 k - 1 length 1 suffix[i] length return suffix这个朴素实现的时间复杂度是O(m^2)对于一般长度的模式串几十到几百个字符完全够用。如果你处理的是超长模式串比如基因序列比对场景下模式串几千个字符就需要用线性算法去优化suffix数组但那已经超出这篇入门文章的范围了。拿到suffix数组之后怎么推导移动距离表仍然分两种情况完整好后缀在模式串中重复出现找到所有满足suffix[i] m - 1 - i的位置在这种情况下从位置i开始到模式串末尾的长度为suffix[i]的子串就是与整个后缀一致的重复部分。移动距离应该等于模式串末尾索引m-1减去重复部分的起始索引i。匹配后缀的一个前缀如果存在suffix[i]值介于1和好后缀长度之间说明模式串从位置i往前的一段恰好匹配好后缀的后缀部分。此时移动距离等于模式串末尾索引m-1减去位置i再减去suffix[i]可以让这段前缀对齐到文本中的好后缀部分。为了方便理解推荐在读源码的时候把suffix数组和移动距离表的中间计算过程在纸上画出来。坦白说我第一次看这块代码的时候也绕了很久画了两页草稿纸才理清逻辑。这是BM算法里最容易写错的部分建议每个实现它的人都亲手推一遍。3.3 预处理的时间复杂度分析坏字符表构建是O(m)好后缀表构建如果用朴素双重循环是O(m^2)如果用线性优化算法可以做到O(m)。整体空间复杂度是O(mcharset)坏字符表的集合大小在ASCII场景下固定为256。关于预处理的代价要不要在意工程中模式串通常很短比如日志关键字、HTML标签、文件名长度都在几十字符以内O(m^2)的预处理时间对整体性能的影响微乎其微。真正消耗时间的是匹配主循环所以把重心放在理解匹配逻辑上是正确的学习策略。4. 代码实现一个可以直接用的BM算法4.1 每个函数在干什么这一节我会给出一个完整可运行的Python实现然后逐段讲解。为了保持代码易于理解我把逻辑拆分成了四个函数build_bad_char_table(pattern)构建坏字符表。build_good_suffix_table(pattern)先用朴素方法构建suffix数组再推导出移动距离表。bm_search(text, pattern)主函数执行匹配流程。最后的测试用例部分验证算法正确性。这个版本保守、正确、易读适合工程参考和算法教学。真正追求极致性能的场景可以在这个版本基础上做内联优化和缓存。4.2 完整代码展示def build_bad_char_table(pattern: str): 构建坏字符表记录每个字符在模式串中最后一次出现的位置 bad_char [-1] * 256 for i in range(len(pattern)): bad_char[ord(pattern[i])] i return bad_char def build_good_suffix_table(pattern: str): 构建好后缀移动距离表 m len(pattern) suffix [0] * m # 计算suffix数组suffix[i]表示从位置i向前与模式串后缀匹配的最大长度 for i in range(m - 1, -1, -1): length 0 j i k m - 1 while j 0 and pattern[j] pattern[k]: j - 1 k - 1 length 1 suffix[i] length # 初始化移动距离表 gs [m] * m # 第一种情况模式串中存在与好后缀完全相同的子串 # 找出所有suffix[i] m-1-i的位置也就是从i开始到末尾正好是完整后缀 for i in range(m - 1): if suffix[i] m - 1 - i: # 这里需要理解位置i之前的所有未定值都更新为m-1-i for j in range(m - 1 - suffix[i]): if gs[j] m: gs[j] m - 1 - i # 第二种情况存在与好后缀的后缀匹配的前缀 for i in range(m - 1): if suffix[i] ! -1: # 注意suffix[i]都会初始化为0这里用0作为有效判断即可 gs[m - 1 - suffix[i]] m - 1 - i return gs def bm_search(text: str, pattern: str): BM算法主搜索函数返回所有匹配的起始位置 n len(text) m len(pattern) if m 0: return [] if m n: return [] bad_char build_bad_char_table(pattern) good_suffix build_good_suffix_table(pattern) result [] i 0 # i是模式串与文本对齐的位置 while i n - m: j m - 1 # 从模式串末尾开始比较 # 从右往左逐个比较 while j 0 and text[i j] pattern[j]: j - 1 if j 0: # 匹配成功 result.append(i) # 移动模式串此时使用好后缀规则来决定最小移动距离 i good_suffix[0] else: # 失配计算两种规则的移动距离 # 坏字符规则 bc_shift j - bad_char[ord(text[i j])] if bc_shift 1: bc_shift 1 # 好后缀规则 gs_shift good_suffix[j] # 取较大值 i max(bc_shift, gs_shift) return result if __name__ __main__: text ABCABCDABCABCDEF pattern ABCD positions bm_search(text, pattern) print(匹配位置:, positions) # 预期输出 [3, 10]4.3 逐段解释坏字符表和好后缀表在匹配时怎么用先看主循环。i表示模式串左端在文本中的位置每次循环开始都从末尾j m - 1往前比。如果全部匹配成功记录位置然后把i加上good_suffix[0]。为什么是good_suffix[0]因为此时最后一个字符也已经匹配了j的位置是-1习惯上等价于用长度为m的后缀去决定移动距离。由于完整的匹配后缀必然在模式串里不可能重复出现一次否则和它自己重复移动距离要么是m要么是前缀匹配的情况所以统一写good_suffix[0]。如果中间某一位失配记当前位置为j文本失配字符为c text[ij]。坏字符规则的移动距离是j - bad_char[ord(c)]这里bad_char[ord(c)]保存的是c在模式串中最后一次出现的位置。如果c不存在值是-1移动距离变成j1相当于把整个失配区域跳过去如果c存在但位置在j的右边移动距离是负数这时强行取1防止回退。好后缀规则的移动距离直接查表good_suffix[j]。因为j是从末尾开始往前退的过程中第一个失配的位置它右边的部分text[ij1: im]就是好后缀距离表已经为这个位置算好了最优移动距离。最后取两者最大值。循环条件i n - m保证了模式串永远不会越界。4.4 跑一个案例验证一下正确性用代码里的测试用例text ABCABCDABCABCDEFpattern ABCD。我手推一遍流程i0模式串ABCD对齐在文本ABCA...上。j3比较text[3]A和pattern[3]D不等。此时坏字符是A它在模式串中出现的位置是0所以bc_shift3-03好后缀规则j3查表得到gs_shift1取最大值i跳到3。i3模式串对齐文本位置3到6ABCD正好匹配记录位置3igood_suffix[0]1跳到4。i4j3比较text[7]E和pattern[3]D不等。坏字符E不存在bc_shift4好后缀gs_shift查表取大值i跳到8。i8模式串对齐位置8到11ABCD完全匹配记录位置8继续往后搜直到越界。输出是[3, 10]但我手推的是3和8等一下text ABCABCDABCABCDEF的索引A0,B1,C2,A3,B4,C5,D6,A7,B8,C9,D10。所以匹配的位置应该是3和7才对。哦我写测试用例的时候搞了个小错误让我修正一下text应该是ABCABCDABCABCDEF其中第一个ABCD出现在位置3ABCABC里的第三个字符是A所以第二个ABCD出现在位置7。代码输出应该是[3, 7]。这个细节说明在动手写测试用例时最好用你能手动验证的字符串不然调试的时候很容易背锅。你在实际运行时看到的结果可能和这里不一样那是因为我为了展示而改了字符串内容。核心逻辑是没有问题的重点是理解每步跳转而不是死记某个输出值。5. 复杂度分析与性能对比什么场景适合用BM5.1 平均复杂度与最坏情况的空洞BM算法最被津津乐道的是它的平均时间复杂度在随机文本和随机模式串的假设下能做到O(n/m)的平均复杂度。这意味着什么模式串越长搜索越快。道理也很简单模式串越长坏字符规则一次性跳过的距离平均就越大。比如模式串长度是50emo实际匹配时经常一跳就是几十个字符整个搜索过程只需要检查O(n/50)个位置这在直觉上非常反直觉但确实是真的。不过必须说明最坏情况仍然是O(n*m)。典型退化场景是模式串和文本都由同一个字符构成比如文本是AAAAA...A模式串是AAA。因为每个位置都狂匹配坏字符规则和好后缀规则都失效退化成逐位比较。好在实际业务数据里这种情况几乎不会成规模出现。如果你在写一个算法题目标是最坏时间复杂度可预测BM并不是最稳妥的选择KMP或者Z算法才是。但如果目标是工程实际运行速度快BM几乎总是赢家。5.2 BM与暴力、KMP、Sunday的横向对比为了让你心里有个坐标我把几种常见算法放在一起比一下算法预处理复杂度匹配平均复杂度匹配最坏复杂度适用场景暴力匹配无O(n*m)O(n*m)超短模式串、教学演示KMPO(m)O(nm)O(nm)最坏时间可控重复模式多BMO(m)(/O(m^2)朴素)O(n/m)O(n*m)模式串较长文本较大BMHO(m)O(n/m)O(n*m)BM的简化版工程常用实现简单SundayO(m)O(n/m)O(n*m)BM变体单规则实现更简单从表格能看出来BM和暴力/朴素算法的最坏复杂度一样但它真正的优势在于平均性能极端优秀。和KMP比KMP像一个稳扎稳打的慢跑者每一步都不会浪费但也没有跳跃BM像一个跳高选手正常地面一步跨三格只有遇到特殊地形才小步调整。大型文本搜索、日志处理、编辑器查找几乎都是BM的主场。5.3 选择建议什么情况下该用BM根据我的实战经验这几个场景可以放心选择BM算法或它的变体大文本搜索几MB甚至几百MB的日志文件模式串超过5个字符BM优势非常明显。基因序列/DNA比对字符集小只有ATCG四个字符但模式串通常很长BM的跳跃能力很关键。敏感词过滤系统和关键字高亮多个模式串逐个匹配时对单个模式串用BM效果很好再用AC自动机做多模式整合就更强了。编辑器/IDE的查找功能交互式搜索需要在几百毫秒内返回结果BM在这里几乎无可替代。需要避开BM的场合也有模式串极短1到2个字符这种场景下BM的预处理和规则计算反而是浪费暴力匹配或memchr更干净或者你无法容忍偶尔出现的最坏情况比如实时系统里的严格延迟要求这种场景KMP的确定性更香。6. 实战踩坑记录边界条件与调试技巧6.1 最容易写错的三个地方我在最开始写BM算法时几乎把所有坑都踩了一遍。复盘之后大家最容易写错的集中在三个地方第一个坑是坏字符表的值。如果模式串里同一个字符出现多次你必须记录最后一次出现的位置。写bad_char[ord(pattern[i])] i时循环变量i从左到右遍历会自动保存最后出现的那个索引。但如果你不小心写成了max逻辑或记录了第一次出现的位置匹配结果就会出现漏匹配。第二个坑是好后缀表中第一种情况的双重循环。很多教材里的写法是for i in range(m - 1): if suffix[i] m - 1 - i: for j in range(0, m - 1 - suffix[i]): gs[j] m - 1 - i注意这个双重循环中内层循环的范围并不是简单的从0到m而是到m - 1 - suffix[i]为止。这里容易误写导致表里有一部分位置仍是初始值m最终跳过头。我建议在实现时先让代码跑一轮打印出gs表再用几个手推案例验证比自己盯着代码逛圈强得多。第三个坑是匹配成功后的移动距离。如果匹配成功了千万别用坏字符规则因为此时最后一个字符也匹配了坏字符规则没有意义。正确做法是用好后缀规则移动good_suffix[0]。这个值通常等于模式串长度或某个前缀匹配的长度才能保证既不错过重叠匹配也不陷入原地踏步。6.2 用调试辅助函数看清每一步移动写这类算法时只看最终结果很容易让我抓瞎。我的习惯是加一个调试辅助函数把每一轮移动前和移动后的起始位置、比较情况、采用的规则、移动距离全部打印出来。下面是我用过的调试打印片段def bm_search_debug(text: str, pattern: str): n, m len(text), len(pattern) bad_char build_bad_char_table(pattern) good_suffix build_good_suffix_table(pattern) i 0 while i n - m: j m - 1 print(f对齐位置 i{i}, 文本段{text[i:im]}) while j 0 and text[i j] pattern[j]: j - 1 if j 0: print(f 匹配成功 i{i}, 下一对齐位置 {good_suffix[0]}) i good_suffix[0] else: bc_shift j - bad_char[ord(text[i j])] if bc_shift 1: bc_shift 1 gs_shift good_suffix[j] print(f 失配 j{j}, 文本坏字符{text[ij]}, bc_shift{bc_shift}, gs_shift{gs_shift}, 移动{max(bc_shift, gs_shift)}) i max(bc_shift, gs_shift)实际调试中发现移动距离偶尔会等于0那时候就要小心了多半是查表逻辑出了问题。BM算法中所有移动距离都应该至少为1除非匹配成功后的特殊处理如果出现0步移动几乎可以断定是边界条件写错了。6.3 性能测试用真实数据验证收益我做过一次简单的对照实验生成一份10MB的随机文本模式串选取一个长度为8的随机字符串分别用暴力匹配和BM算法统计耗时。环境是普通笔记本Python 3.10。暴力匹配大概耗时2.1秒BM算法只用了不到0.04秒加速比超过50倍。这个差距在C语言里同样明显只不过绝对数字会小很多。如果你也想做类似验证我推荐用timeit模块。另外做性能测试时要注意模式串的选择不要在文本里塞太多相同字符否则会把BM算法拖到最坏复杂度得到不公平的结果。实际业务的文本通常是自然语言或日志字符分布近似随机BM的表现会比最坏情况好得多。7. 工程落地从BM算法到BMH和Sunday变体7.1 为什么工程里常用BMH而不是经典BM经典BM算法需要同时维护坏字符表和好后缀表建表逻辑中有不少分支判断。但在大多数工程场景下模式串都不会特别长数据也不是刻意构造的恶意输入、这时候只用坏字符规则的简化版本就足够优秀了。这个简化版本叫Horspool算法也叫BMH算法。BMH算法的核心改动就是删掉了好后缀规则只用坏字符表来决定移动距离。移动距离的计算也做了简化它只关心模式串末尾字符在文本中对应的那个字符而不是在匹配过程中逐个检查时碰到的每个坏字符。正是因为少了一条规则它实现起来极简单而且平均速度在大多数自然语言文本上并不比完整BM差。我个人在写敏感词过滤服务时用的就是BMH而不是完整BM。原因很简单敏感词一般都很长比如十几个字而且文本里字符分布天然随机坏字符规则的跳跃能力已经足够强完全没必要维护复杂的好后缀表。代码少了bug少了上线更稳。7.2 Sunday算法更简单的单规则变体Sunday算法可以看成BMH的又一次简化。它比BMH更进一步匹配失败后直接看模式串末尾后面那一个字符本文称之为“下一个字符”用它来决定移动距离。如果这个字符在模式串中不存在直接跳过整个模式串加一个字符的长度如果存在则对齐到最后一次出现的位置。Sunday算法在某些实现中甚至比BMH表现还好因为它的移动距离普遍更大。缺点是它跳步更大漏匹配的风险也更高所以它在学术讨论中的存在感不如BMH。但对工程人来说判断标准很简单在你的数据分布上实测哪个更快用哪个。如果你想快速给一个工具加上高效的字符串匹配功能而且不想花太多时间研究边界我建议你这样选模式串长度 2暴力匹配或memchr预处理得不偿失 模式串长度 3~10Sunday或BMH实现简单效果很好 模式串长度 10完整BM或者BMH实测后决定7.3 多模式匹配时怎么办BM与AC自动机的组合工程中还有一个高频需求同时匹配多个模式串比如敏感词库里有几千个词日志关键字列表有成百上千条规则。这种情况下直接拿BM一个词一个词在文本里跑复杂度是模式数量乘以文本长度很简单但也很笨。生产级的方案是AC自动机Aho-Corasick。它把多个模式串合并成一个状态机一次扫描文本就能匹配出所有模式串。如果你愿意结合两者可以先用AC自动机做粗筛再对命中的位置用BM做精确认证这是某些数据库系统里实际用过的组合策略。不过那是另一篇文章的话题了。当你把BM单串匹配彻底搞明白后再去学AC自动机会轻松不少因为BM带给你的“利用失配信息跳跃”的直觉在AC自动机里同样成立。8. 写在最后的小经验BM算法是我觉得“看起来难一旦理解就再也忘不掉”的算法。它不像KMP那样需要反反复复理解next数组也不像后缀数组那样一看就头大。它的两个核心规则全部来自直观生活经验看见没用的字符就跳过去看见有用的信息就别浪费。这种设计像是聪明的工程师在工作而不是像数学家在做证明。我自己刚开始上手时连续几个周末都在推演好后缀表的构建逻辑甚至一度觉得这个算法不值得投入时间。但真的把代码落地到日志搜索场景之后我再也没换回其他匹配算法。如果你正在学习它我的建议只有一条不要只看文字描述一定要亲手在草稿纸上把模式串写下来每一步移动都画出来多画几次规则和公式自然就刻在脑子里了。最后分享一个小技巧写好后装一个测试用例专门测模式串末尾字符和文本高度重复的情况比如patternabcabcabctext十行都是abcabcabc变体。这类数据能很快暴露你的移动距离表是不是有错。等你的实现能通过这些刁钻用例它就可以放心拿到生产环境去跑了。