BM算法详解：坏字符与好后缀规则及高效字符串匹配实现

1. 从暴力匹配的痛点说起：为什么需要BM算法

字符串匹配这件事，乍一看特别简单。给你一个主串，比如一段几万字的文本，再给你一个模式串，比如一个关键词，让你找出模式串在主串里出现的位置。很多人第一反应就是两层循环硬怼：外层遍历主串的每个起始位置，内层逐字符比对。这个方法学名叫BF算法，也就是暴力匹配。

我最早写代码的时候就是这么干的，逻辑清晰，闭着眼都能写出来。但问题在于，当主串长度是n、模式串长度是m的时候，最坏情况下时间复杂度是O(n*m)。什么概念呢？假设主串是一篇十万字的小说，模式串是一个二十字的句子，最坏情况要比较两百万次。如果这个匹配操作还要在循环里反复调用，比如做敏感词过滤、日志检索、代码编辑器的查找替换，那性能直接就崩了。

后来我接触到了KMP算法，它的核心思路是利用已经匹配过的信息，通过一个next数组记录模式串自身的重复结构，从而在失配时不让主串指针回退。KMP把时间复杂度降到了O(n+m)，这已经是很了不起的改进了。但KMP有一个特点：它是从左往右逐字符比较的，每次失配后模式串向右滑动的距离，依赖于模式串前缀和后缀的匹配情况。在某些场景下，这个滑动距离并不够大。

BM算法，全称Boyer-Moore算法，走的是另一条路。它最反直觉的地方在于：比较的方向是从右往左。也就是说，模式串和主串对齐之后，先比较模式串的最后一个字符，然后依次往前比。这个设计初看很奇怪，但正是这个"从右往左"的策略，让BM算法能够在失配时获得更大的滑动距离，从而跳过更多不可能匹配的位置。

BM算法在实际应用中非常能打。根据一些工程实践的数据，在处理自然语言文本时，BM算法的实际比较次数往往远低于KMP，甚至在某些情况下接近O(n/m)。这也是为什么很多工业级的字符串查找工具，比如文本编辑器的搜索功能、grep的某些实现，都会选择BM或者它的简化版本作为底层算法。

这篇文章我会把BM算法的两个核心规则——坏字符规则和好后缀规则——拆开揉碎讲清楚，然后给出完整的代码实现，最后聊聊实际工程中怎么用、有哪些坑。如果你正在准备面试，或者想在自己的项目里做一个高效的字符串查找模块，这篇内容应该能帮到你。

2. 坏字符规则：失配时模式串该往右滑多远

2.1 什么是坏字符

BM算法从右往左比较，当某个位置的字符对不上时，主串中那个对不上的字符就叫坏字符。举个例子，主串是"HERE IS A SIMPLE EXAMPLE"，模式串是"EXAMPLE"。对齐之后从右往左比，模式串的最后一个字符是'E'，主串对应位置是'S'，对不上，那么'S'就是坏字符。

坏字符规则要解决的问题是：既然'S'和'E'对不上，那模式串应该往右滑动多少位，才有可能让'S'和模式串中的某个字符对上？

这里分两种情况。

第一种情况：坏字符在模式串中不存在。比如上面的例子，'S'在"EXAMPLE"里根本没有出现。那意味着什么？意味着模式串无论怎么滑，只要'S'还落在模式串覆盖的范围内，就不可能匹配成功。所以直接把模式串滑到坏字符的右边，也就是滑动距离等于坏字符在模式串中的位置到模式串末尾的距离。

第二种情况：坏字符在模式串中存在。那就要找到坏字符在模式串中最靠右出现的位置，然后把模式串滑动到让那个位置和主串中的坏字符对齐。

2.2 滑动距离的计算

假设模式串长度为m，坏字符在主串中的位置为i（相对于模式串的起始位置），坏字符在模式串中最靠右出现的位置为j（从0开始计数）。那么滑动距离就是 i - j。

如果坏字符在模式串中不存在，我们令j = -1，滑动距离就是 i - (-1) = i + 1。

这里有一个关键点：如果坏字符在模式串中靠右出现的位置大于i，那计算出来的滑动距离可能是负数。这种情况说明什么？说明坏字符虽然在模式串里出现了，但它出现的位置在坏字符当前位置的右边。如果按照这个距离滑动，模式串反而会往左走，这显然是不对的。所以实际实现中，我们会取滑动距离和1的较大值，保证模式串至少往右滑一位。

我当初理解这个规则的时候，画了好几遍图才搞明白。你可以这样想：坏字符规则的本质是"对齐"。主串里有个字符和模式串对不上，那我就看看这个字符在模式串里最靠右出现在哪，把它俩对齐，这样才有可能继续匹配。

2.3 坏字符规则的局限性

坏字符规则单独用的时候有一个明显的问题：它可能产生负向滑动。虽然我们可以用max(1, distance)来兜底，但这意味着在某些情况下，坏字符规则给出的滑动距离非常小，甚至退化成每次只滑一位。这时候BM算法的效率就会大打折扣。

举个经典的例子：主串是"AAAAAAAAAAAAAAAA"，模式串是"BAAAA"。从右往左比，模式串最后一个字符是'A'，主串对应位置也是'A'，匹配；继续往前比，模式串倒数第二个字符是'A'，主串也是'A'，匹配；一直到模式串第一个字符'B'，主串对应位置是'A'，失配。坏字符是'A'，它在模式串中最靠右出现的位置是4（最后一个位置）。按照坏字符规则，滑动距离是0 - 4 = -4，取max(1, -4) = 1。也就是说，每次只能滑一位。这种情况下，BM算法退化成和暴力匹配差不多。

正是为了解决这个问题，BM算法引入了第二个规则：好后缀规则。

3. 好后缀规则：利用已经匹配的部分加速滑动

3.1 好后缀的基本概念

好后缀规则的核心思想是：当模式串的某个后缀和主串匹配成功，但在更前面的位置失配时，我们已经知道主串中有一段字符和模式串的后缀是一样的。那能不能利用这个信息，让模式串滑得更远？

还是用例子来说明。主串是"HERE IS A SIMPLE EXAMPLE"，模式串是"EXAMPLE"。假设我们已经比较到了某个位置，模式串的后缀"MPLE"和主串匹配上了，但在更前面失配了。这时候"MPLE"就是好后缀。

好后缀规则要问的问题是：模式串中还有没有其他地方也出现了"MPLE"这个子串？或者，"MPLE"的某个后缀是不是模式串的前缀？

3.2 三种滑动情形

好后缀规则根据模式串中好后缀的出现情况，分三种情形处理。

情形一：模式串中存在另一个完整的好后缀。比如好后缀是"MPLE"，模式串中在更靠左的位置也出现了"MPLE"。那就把模式串滑动到让这两个"MPLE"对齐的位置。

情形二：好后缀的后缀是模式串的前缀。比如好后缀是"MPLE"，模式串中没有另一个完整的"MPLE"，但"PLE"或者"LE"或者"E"是模式串的前缀。那就找到最长的那个后缀，把它和模式串的前缀对齐。

情形三：好后缀在模式串中既没有完整出现，它的后缀也不是模式串的前缀。这种情况下，直接把模式串滑到好后缀的右边。

3.3 好后缀滑动距离的计算

好后缀规则的计算比坏字符规则要复杂一些，因为它涉及到对模式串自身的预处理。通常的做法是维护两个数组：suffix数组和prefix数组。

suffix数组的含义是：suffix[i]表示模式串从位置i开始的后缀，与模式串的某个后缀的最长公共部分长度。听起来有点绕，换个说法：suffix[i]记录的是，模式串中以i为起点的子串，和模式串的某个后缀能够匹配上的最大长度。

prefix数组则用来标记：模式串的某个后缀是否是模式串的前缀。

具体的预处理过程我放在后面的代码实现里详细讲。这里你只需要理解一个核心逻辑：好后缀规则给出的滑动距离，是"模式串中好后缀上一次出现的位置"到"好后缀当前位置"的距离。如果好后缀在模式串中没有完整出现，那就找它的最长后缀，看这个后缀是不是模式串的前缀，如果是，滑动到对齐的位置；如果不是，直接滑过整个好后缀。

3.4 两个规则怎么选

坏字符规则和好后缀规则各自都能给出一个滑动距离。BM算法的做法是：取两个距离中较大的那个。这样做的理由是，两个规则给出的都是"安全"的滑动距离，也就是说，滑动这么多位之后，不会错过任何可能的匹配。既然都安全，那当然滑得越远越好。

这个"取较大值"的策略，是BM算法高效的关键。坏字符规则在字符集较大的时候（比如英文文本）效果很好，因为坏字符在模式串中不出现的概率高，滑动距离大。好后缀规则则在模式串有重复结构的时候发挥威力，弥补坏字符规则可能只滑一位的缺陷。

我个人的经验是，在实际实现中，好后缀规则的预处理虽然麻烦一点，但它带来的性能提升是值得的。尤其是在模式串较长、字符集较小（比如DNA序列只有四种字符）的场景下，好后缀规则几乎是必须的。

4. 手写一个BM算法：从预处理到匹配的完整实现

4.1 坏字符表的构建

坏字符规则的预处理相对简单，核心就是构建一张坏字符表，记录每个字符在模式串中最靠右出现的位置。

def build_bad_char_table(pattern): """ 构建坏字符表 返回一个字典，key是字符，value是该字符在模式串中最靠右出现的位置 如果字符不在模式串中，则不在字典中，查询时默认返回-1 """ table = {} for i, ch in enumerate(pattern): table[ch] = i return table

这张表的作用是：当我们在主串中遇到坏字符时，直接查表得到它在模式串中最靠右的位置。如果查不到，说明坏字符不在模式串中，位置记为-1。

这里有一个细节需要注意：构建坏字符表时，如果同一个字符在模式串中多次出现，后面的位置会覆盖前面的位置。这正是我们想要的，因为我们需要的是最靠右的出现位置。

4.2 好后缀数组的预处理

好后缀的预处理要复杂一些。我们需要构建suffix数组和prefix数组。

def build_good_suffix_table(pattern): """ 构建好后缀规则所需的suffix和prefix数组 suffix[i]表示模式串中以i为起点的子串与模式串后缀的最长匹配长度 prefix[i]表示模式串长度为i的后缀是否是模式串的前缀 """ m = len(pattern) suffix = [0] * m prefix = [False] * m # 从后往前遍历，计算suffix数组 for i in range(m - 1): j = i k = 0 # 从位置i开始，与模式串末尾逐字符比较 while j >= 0 and pattern[j] == pattern[m - 1 - k]: j -= 1 k += 1 suffix[k] = i + 1 # k是匹配长度，i+1是起始位置+1 # 计算prefix数组 for i in range(1, m): if pattern[i] == pattern[0]: # 检查从i开始的后缀是否是模式串的前缀 j = i k = 0 while j < m and pattern[j] == pattern[k]: j += 1 k += 1 if j == m: prefix[k] = True return suffix, prefix

这段代码的逻辑是：对于模式串的每个位置i，计算以i为起点的子串和模式串后缀的最长公共部分长度。suffix[k]记录的是长度为k的公共部分对应的起始位置。

prefix数组则标记模式串的哪些长度的后缀同时也是模式串的前缀。

4.3 滑动距离的计算函数

有了坏字符表和好后缀数组，接下来需要写一个函数来计算每次失配时的滑动距离。

def get_good_suffix_shift(m, suffix, prefix, bad_char_pos): """ 根据好后缀规则计算滑动距离 m: 模式串长度 suffix, prefix: 预处理得到的数组 bad_char_pos: 坏字符在模式串中的位置（从右往左比较时的位置） """ # 好后缀的长度 good_suffix_len = m - 1 - bad_char_pos # 情形一：模式串中存在另一个完整的好后缀 if suffix[good_suffix_len] != 0: return m - suffix[good_suffix_len] # 情形二：好后缀的后缀是模式串的前缀 for i in range(good_suffix_len, m): if prefix[i]: return m - i # 情形三：直接滑过整个好后缀 return m

这个函数的逻辑是：先看模式串中是否有另一个完整的好后缀，如果有，滑动到那个位置；如果没有，找好后缀的最长后缀，看它是不是模式串的前缀，如果是，滑动到对齐的位置；如果都不是，直接滑过整个好后缀。

4.4 完整的BM算法实现

把上面的部分组合起来，就是完整的BM算法。

def bm_search(text, pattern): """ BM算法字符串匹配 返回模式串在主串中第一次出现的位置，如果没有找到返回-1 """ n = len(text) m = len(pattern) if m == 0: return 0 if n < m: return -1 # 预处理 bad_char_table = build_bad_char_table(pattern) suffix, prefix = build_good_suffix_table(pattern) # 主循环 i = 0 # 主串中当前对齐的起始位置 while i <= n - m: j = m - 1 # 从模式串末尾开始比较 # 从右往左比较 while j >= 0 and text[i + j] == pattern[j]: j -= 1 if j < 0: # 匹配成功 return i # 计算坏字符规则的滑动距离 bad_char = text[i + j] bad_char_pos = bad_char_table.get(bad_char, -1) bad_char_shift = j - bad_char_pos # 计算好后缀规则的滑动距离 good_suffix_shift = get_good_suffix_shift(m, suffix, prefix, j) # 取较大值，保证至少滑动一位 i += max(bad_char_shift, good_suffix_shift, 1) return -1

4.5 测试与验证

写完之后一定要用几个典型用例验证一下。

# 测试用例 test_cases = [ ("HERE IS A SIMPLE EXAMPLE", "EXAMPLE", 17), ("AAAAAAAAAAAAAAAA", "BAAAA", -1), ("ABCABCDABABCDABCDABDE", "ABCDABD", 15), ("hello world", "world", 6), ("hello world", "xyz", -1), ("a", "a", 0), ("abc", "abcd", -1), ] for text, pattern, expected in test_cases: result = bm_search(text, pattern) status = "通过" if result == expected else "失败" print(f"[{status}] 主串='{text}', 模式串='{pattern}', 期望={expected}, 实际={result}")

这几个用例覆盖了：正常匹配、不匹配、模式串有重复结构、模式串比主串长、单字符匹配等情况。跑一遍确认都通过，基本就没大问题了。

注意：好后缀数组的预处理是BM算法实现中最容易出错的部分。建议在写完之后，单独对suffix和prefix数组做单元测试，用简单的模式串（比如"ABAB"、"AAAA"）手动验证数组的值是否正确。

5. 实际工程中的优化与踩坑记录

5.1 字符集大小对性能的影响

坏字符规则的效果和字符集大小密切相关。字符集越大，坏字符在模式串中不出现的概率越高，滑动距离就越大。英文文本的字符集大概是26个字母加上标点符号，效果不错。但如果处理的是二进制数据，字符集是256，坏字符规则的效果会更好。反过来，如果处理的是DNA序列，字符集只有4种，坏字符规则的效果就会打折扣，这时候好后缀规则的重要性就凸显出来了。

我在一个日志检索的项目里用过BM算法，日志内容是英文和数字混合，字符集大概六七十种。实测下来，BM算法的比较次数比KMP少了大概40%左右。但如果把同样的算法用在纯数字的匹配上，优势就没那么明显了，因为数字只有10种，坏字符规则经常给出很小的滑动距离。

5.2 内存与预处理的权衡

BM算法的预处理需要额外的空间来存储坏字符表和好后缀数组。坏字符表的大小取决于字符集，好后缀数组的大小等于模式串长度。对于短模式串来说，这点内存开销可以忽略不计。但如果模式串很长，比如几千个字符，好后缀数组的预处理时间就不能忽视了。

我遇到过一个场景：模式串是动态生成的，每次匹配都要重新预处理。这种情况下，BM算法的预处理开销反而成了瓶颈。后来我的做法是，如果模式串长度小于某个阈值（比如8），直接用暴力匹配；如果大于阈值，再用BM算法。这个阈值需要根据实际场景测试来确定，没有绝对的标准。

5.3 好后缀预处理的常见Bug

好后缀数组的预处理是BM算法实现中最容易出Bug的地方。我踩过的坑包括：suffix数组的索引越界、prefix数组的标记逻辑错误、好后缀长度为0时的边界处理。

有一个特别隐蔽的Bug：当好后缀的长度等于模式串长度时（也就是整个模式串都匹配上了），按照好后缀规则计算出来的滑动距离可能是0。这时候如果不做特殊处理，程序会陷入死循环。解决办法是在取滑动距离的时候，强制保证至少为1。

还有一个坑是：坏字符规则计算出的滑动距离可能是负数，好后缀规则计算出的滑动距离可能是0。这两个值取max之后，如果还是0或者负数，就必须强制设为1。我在代码里用max(bad_char_shift, good_suffix_shift, 1)来兜底，这样就不会出现不滑动的情况。

5.4 什么时候不该用BM算法

BM算法虽然高效，但并不是所有场景都适合。如果模式串非常短（比如长度1到3），BM算法的预处理开销和额外的逻辑判断反而会让它比暴力匹配还慢。这种情况下，直接用暴力匹配或者KMP更合适。

另外，如果主串和模式串的字符集非常小（比如只有两种字符），坏字符规则基本失效，好后缀规则虽然能工作，但整体性能提升有限。这种场景下，KMP或者Sunday算法可能是更好的选择。

还有一个实际因素：代码复杂度。BM算法的实现比KMP复杂不少，尤其是好后缀规则的预处理。如果项目对性能的要求不是特别极致，用KMP或者内置的字符串查找函数可能更省事。我个人的原则是：先用最简单的方案跑通，确认性能瓶颈确实在字符串匹配上，再考虑上BM算法。

6. 和其他匹配算法的横向对比

6.1 BM vs KMP

KMP的核心是next数组，利用模式串自身的重复结构来避免主串指针回退。BM的核心是坏字符和好后缀两个规则，利用从右往左比较获得的信息来最大化滑动距离。

从时间复杂度上看，两者都是O(n+m)级别的。但在实际运行中，BM算法的比较次数通常更少，尤其是在字符集较大的场景下。KMP的优势在于实现相对简单，而且不需要额外的字符集相关的预处理。

我个人的选择习惯是：如果模式串是固定的、需要反复匹配（比如敏感词过滤），用BM算法，因为预处理只做一次，后续匹配效率高。如果模式串是动态的、每次都不一样，用KMP可能更划算，因为KMP的预处理更轻量。

6.2 BM vs Sunday算法

Sunday算法是BM算法的一个简化版本，它的核心思想是：当失配时，看主串中参与匹配的部分的下一个字符，然后根据这个字符在模式串中的位置来决定滑动距离。Sunday算法的实现比BM简单很多，而且在很多场景下性能并不差。

我做过一个简单的对比测试：在英文文本中查找长度为10的模式串，BM算法和Sunday算法的比较次数差距在10%以内。但Sunday算法的代码量只有BM的三分之一左右。所以如果你的项目对代码复杂度有要求，Sunday算法是一个很好的折中方案。

6.3 各算法适用场景总结

这张表是我根据实际使用经验总结的，不一定全面，但能覆盖大部分常见情况。选哪个算法，最终还是要看具体的业务需求、性能指标和团队的技术栈。

7. 我在实际项目中的使用心得

BM算法我用了大概有三四年，踩过的坑和积累的经验也不少。分享几个我觉得比较有价值的点。

第一，不要过早优化。我见过一些项目，字符串匹配的量级根本不大，但开发者一上来就手写BM算法，结果代码复杂、维护成本高，性能提升却微乎其微。先用最简单的方案，用性能分析工具确认瓶颈，再决定要不要上BM。

第二，好后缀规则的预处理可以简化。如果你的场景对性能要求不是极致，可以只实现坏字符规则，跳过好后缀规则。这样代码量减少一半，性能虽然有所下降，但在很多场景下仍然比暴力匹配快得多。我早期的一个项目就是这么干的，跑了一年多也没出问题。

第三，测试用例要覆盖边界情况。模式串为空、模式串比主串长、模式串和主串完全相同、模式串在主串末尾匹配、模式串中有大量重复字符，这些情况都要测到。我当初就是因为没测模式串全重复的情况，上线后才发现性能退化的问题。

第四，善用语言内置的字符串查找。Python的str.find()、Java的String.indexOf()、C++的std::string::find()，底层实现通常都是高度优化的，很多就是BM或者其变种。在大多数业务场景下，直接用内置函数就够了，没必要自己造轮子。自己实现BM算法的价值，更多在于理解算法思想，以及在特殊场景下做定制化优化。

第五，关注实际数据分布。BM算法的性能高度依赖于主串和模式串的字符分布。在英文文本中表现很好，在中文文本中可能就没那么理想，因为中文字符集大，但常用字的重复率高，坏字符规则的效果会打折扣。如果你的场景是中文匹配，建议先做性能测试再决定用不用BM。

最后说一个我个人的体会：字符串匹配算法看起来是计算机科学里很基础的内容，但真正在工程中用好，需要对数据特征、性能指标、代码复杂度做综合权衡。BM算法是一个很好的工具，但不是银弹。理解它的原理和适用边界，比会背代码更重要。