如果你平时写代码经常需要在长文本里找一个短字符串大概率用过系统自带的indexOf或者朴素的双层循环。真正让我开始认真研究字符串算法是因为一次日志分析任务几 GB 的文本里反复检索上百个关键词朴素匹配慢到让人怀疑人生。后来接触了 BM 算法Boyer-Moore用一个大文件实测搜索速度肉眼可见提升。这个字符串算法在文本编辑器、查找替换、内容过滤、病毒特征码匹配等场景里都被大量使用核心思路却非常简单匹配时从右往左看失配时用“坏字符”和“好后缀”两条规则尽量大步跳跃而不是老老实实一格一格挪。这篇文章不打算只堆公式我会把两张预处理表从原理到代码完整拆一遍再附一份可以直接复跑 Java 实现最后聊聊我自己调 BM 时踩过的一些坑。不管你是刚接触字符串匹配的新手还是想深入源码级优化的老手应该都能在这里找到点有用的东西。1. 从暴力匹配到 BM为什么匹配时要从右往左看先说清楚 BM 解决了什么问题。朴素的字符串匹配思路很简单把模式串放在文本开头从左到右逐位比较失配就整体右移一格直到文本末尾。这种方案最坏情况下比较次数是模式串长度乘以文本长度也就是 O(n*m)。文本一长比如几十 MB 的日志文件再叠加几十上百个关键词耗时就会被放大得非常恐怖。KMP 算法是另一种经典方案它利用模式串自身的前后缀信息失配时避免从头再比达到线性复杂度 O(nm)。KMP 在算法竞赛和原理教材里地位很高但工程实践中很多文本处理库选 BM 而不是 KMP原因在于一个细节KMP 仍然把匹配失败的“坏消息”当成普通事件处理而 BM 更激进——它把失配字符本身当成一张情报。BM 是否高效的关键在比较顺序。朴素匹配和 KMP 都是从左往右比BM 反过来从模式串的末尾往开头比。为什么从右往左更聪明用一个例子说明模式串是example长度 7当前对齐位置 i 上文本末尾字符是x而模式串最后一个字符是e。从左往右匹配时可能前面六个字符全相等最后一位才暴露失配但从右往左匹配时第一个字符就直接暴露失配而且我们能立刻知道失配字符是x随后根据坏字符规则可能一次跳过一大段。这个差异可以用实际数据量化。假设文本字符集比较大比如英文大小写加标点和空格从右往左比较时绝大多数情况第一次就失配失配字符又大概率不在模式串里于是模式串可以直接跳过整个长度。理想情况下BM 平均比较次数可以接近 O(n/m)也就是说文本越长、模式串越长相对收益越明显。KMP 的线性复杂度是理论上的最优阶但 BM 在“平均表现”上经常赢在实际常数上。当然 BM 最坏情况下会退化到 O(n*m)比如模式串和文本都只有同一个字符此时坏字符和好后缀都发挥不出跳跃能力只能一格一格走。工程实现通常加一个 Galil 优化保证最坏复杂度降到 O(n)。后面我会提到这个优化但核心两张表必须优先讲透。2. 核心一坏字符规则到底在做什么坏字符规则是 BM 两张表里更容易理解的一张。它的思想是当失配发生时拿失配位置的文本字符去查找它在模式串里最后一次出现的位置然后据此计算模式串右移的距离。形式化定义假设模式串长度为 m当前对齐位置为 i我们从模式串末尾开始往左比较失配时模式串位置是 j此时文本中的失配字符叫c text[ij]。模式串里如果存在字符c取其最后一次出现的位置k那么模式串可以安全右移j - k位如果模式串里根本没有c则右移j 1位让失配字符整体落在窗口左侧之外。为什么取“最后一次出现”而不是“第一次出现”因为我们必须保证移动后不会把一个可能匹配的位置错过。如果模式串中c出现多次移动太多会让最后一次出现的c滑到失配字符左边那个位置可能是匹配起点而如果移动太少又没必要。只有让“离失配位置最近的那次出现”来对齐文本失配字符才是不多不少的安全界限。看上图的教科书经典例子文本HERE IS A SIMPLE EXAMPLE模式串EXAMPLE开始比较text[6]这个位置是空格模式串里没有空格于是直接右移 7 位。再比较新对齐位置文本还是空格不对因为此时失配可能是另一个字符但同样可以大步跳跃。这个规则让模式串经常“跳”掉大段明显不可能匹配的文本。坏字符表的构建只需要扫一遍模式串记录每个字符最后一次出现的下标即可。因为要加速 lookup通常用一个长度为字符集大小的数组如果字符集是 ASCII256 大小的数组就够了处理一般 Javachar用 65536 大小工程上如果处理 Unicode 码点就得用HashMapInteger, Integer或类似结构。下面这份 Java 代码展示了坏字符表的构建private static int[] buildBadCharTable(String pattern) { int[] badChar new int[65536]; // 覆盖 char 范围避免 HashMap 的装箱开销 Arrays.fill(badChar, -1); for (int i 0; i pattern.length(); i) { badChar[pattern.charAt(i)] i; } return badChar; }使用时的位移是int bcShift j - badChar[text.charAt(i j)]; if (bcShift 1) { bcShift 1; }这里有个细节必须注意badChar[c]如果返回 -1说明字符 c 完全没在模式串中出现位移是j 1如果返回的位置 k 比 j 还大说明 c 最靠右的出现位置在失配位置右边此时直接计算位移是负数。位移为负没有意义BM 里统一保底为 1。这个负数情况常被初学者忽略造成死循环式的不推进。3. 核心二好后缀规则如何把匹配失误变成经验坏字符规则已经很实用但仍然漏掉一类重要信息如果失配时模式串末尾已经成功匹配了几个字符这几个字符组成的“好后缀”可能在其他位置再次出现。利用好后缀去决定位移就是 BM 的第二张表——好后缀表也叫 gs 表。设想你正在匹配ABCDBC已经成功匹配了最后两个字符BC但再往前一位失配。你的第一反应应该是模式串里别的地方是否还有出现BC如果模式串是BCABCDBC前面从上到下扫一眼开头就有一个BC那就直接把模式串右移让前面的BC对齐到文本里刚匹配好的BC上。这个动作和 KMP 的 next 跳跃非常相似但 BM 多了一个严格约束移动后失配位置对应的新字符不能和原失配字符相同否则这次“跳跃”是无效的——移动过去还会在同一个文本字符上再次失配。这一点非常容易踩坑很多初版实现漏掉这个判断导致好后缀表构建错误匹配结果却看似正常。好后缀的处理分三种情况第一种好后缀在模式串其他位置完整出现过。这种情况位移量是“把好后缀最后一次出现的位置对齐到当前匹配位置”。为了确保不跳过可能匹配一般选择靠右的那次出现。第二种好后缀没有完整重复出现但好后缀的某个后缀恰好等于模式串的一个前缀。这种情况位移量是“把前缀拉到与好后缀的这一截对齐”。第三种以上两种情况都不存在。此时模式串可以安全地整体向后移动 m 位从头开始新一轮匹配。构建好后缀表的方式有很多。标准算法利用suffix[i]数组在线性时间构建但线性版本对边界下标非常敏感稍不留神就写错。我这里给一个不用动太多脑子但正确性容易验证的“暴力校验法”对每个已匹配后缀长度 L枚举所有可能的移动距离 d检查移动后是否满足两个条件满足则取最小 d。两个条件是原匹配窗口内的每个字符移动到新位置后如果新位置还在模式串覆盖范围内那么新旧字符必须相等原失配位置移动到新位置后如果新失配位置还有对应字符那么该字符必须与原失配字符不同。把两个条件翻译成 Java 代码就是下面这个构建函数private static int[] buildGoodSuffixTable(String pattern) { int m pattern.length(); int[] gs new int[m 1]; gs[0] 1; gs[m] 1; // 整个串匹配成功后最小安全位移是 1 for (int L 1; L m; L) { int j m - 1 - L; // 失配位置 int d; for (d 1; d m; d) { boolean ok true; // 条件一原匹配窗口的重叠部分必须仍相等 for (int t m - L; t m; t) { int newIndex t - d; if (newIndex 0 pattern.charAt(newIndex) ! pattern.charAt(t)) { ok false; break; } } if (!ok) continue; // 条件二失配位置的新字符不能和原失配字符相同 int newFail j - d; if (newFail 0 pattern.charAt(newFail) pattern.charAt(j)) { ok false; } if (ok) { break; } } gs[L] d m ? d : m; } return gs; }这段代码的时间复杂度是 O(m^3)模式串长度在几百时完全可用。工程实现为了极致性能会用 suffix 数组优化到 O(m)但优化的下标推导很绕我建议先跑通暴力版本再用标准的线性构建替换。反正两张表都在预处理阶段完成模式串哪怕几千字符暴力构建也慢不到哪里去。用好后缀表时逻辑很简单失配后从表里查出当前已经匹配后缀长度 L 对应的位移gs[L]和坏字符位移取最大值。4. 可复现的 Java 实现坏字符表、好后缀表与主循环把两张表合到一起就是一个可以直接运行的 BM 搜索类。完整代码我放在下面用 Java 写避免依赖任何第三方库。import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class BoyerMooreSearch { private static int[] buildBadCharTable(String pattern) { int[] badChar new int[65536]; Arrays.fill(badChar, -1); for (int i 0; i pattern.length(); i) { badChar[pattern.charAt(i)] i; } return badChar; } private static int[] buildGoodSuffixTable(String pattern) { int m pattern.length(); int[] gs new int[m 1]; gs[0] 1; gs[m] 1; for (int L 1; L m; L) { int j m - 1 - L; int d; for (d 1; d m; d) { boolean ok true; for (int t m - L; t m; t) { int newIndex t - d; if (newIndex 0 pattern.charAt(newIndex) ! pattern.charAt(t)) { ok false; break; } } if (!ok) continue; int newFail j - d; if (newFail 0 pattern.charAt(newFail) pattern.charAt(j)) { ok false; } if (ok) break; } gs[L] d m ? d : m; } return gs; } public static ListInteger searchAll(String text, String pattern) { ListInteger result new ArrayList(); int n text.length(); int m pattern.length(); if (m 0 || n m) { return result; } int[] badChar buildBadCharTable(pattern); int[] gs buildGoodSuffixTable(pattern); int i 0; while (i n - m) { int j m - 1; while (j 0 text.charAt(i j) pattern.charAt(j)) { j--; } if (j 0) { result.add(i); i gs[m]; } else { int L m - 1 - j; int bcShift j - badChar[text.charAt(i j)]; if (bcShift 1) { bcShift 1; } i Math.max(bcShift, gs[L]); } } return result; } public static void main(String[] args) { String text HERE IS A SIMPLE EXAMPLE; String pattern EXAMPLE; System.out.println(searchAll(text, pattern)); } }主循环的写法有几个关键点。外层i表示模式串左边界在文本里的位置循环条件i n - m保证不会越界访问。内层j从m - 1往前递减一旦失配就跳出。如果j 0说明整个模式串匹配成功记录当前位置然后向右移动gs[m]个字符继续找。注意这里gs[m]我设为 1也就是说匹配成功后只后移一格这会让重叠匹配也能被正确找出来比如在AAAA里找AA能返回 0、1、2 三个位置。如果想更高效可以再写一个专门处理“匹配成功后的位移”的数组但教学版本保持简单。用经典例子跑一遍文本HERE IS A SIMPLE EXAMPLE模式串EXAMPLE。第一轮从位置 0 开始比较text[6]发现是空格不是E坏字符表中空格为 -1位移j 1 7直接跳到位置 7。第二轮比较位置 13 的字符发现仍然失配又跳 7 步到位置 14。第三轮从位置 14 开始逐位比较成功匹配整个EXAMPLE返回[14]。整个搜索只比较了十几个字符而不是从头到尾把每个位置都比一遍。5. 实战对比什么时候该用 BM 而不是 KMP在工程选型时很多人默认 KMP 更好因为最坏复杂度是线性的。但实测下来BM 在大多数真实场景里明显更快原因在于它平均跳得快。这里贴一张我自己的对比表供你参考维度朴素匹配KMPBM比较方向从左到右从左到右从右到左失配时利用信息无模式串前后缀坏字符 好后缀预处理空间O(1)O(m)O(m)平均比较次数O(n*m)O(nm)远小于 n理想约 n/m最坏复杂度O(n*m)O(nm)O(n*m)可加 Galil 优化适合场景教学、超短文本保证线性上界、二进制序列大文本短模式、较大字符集这里有一个容易混淆的点KMP 的最坏复杂度 O(nm) 是数学上更漂亮的上界BM 最坏会退化。但如果你平时匹配的是自然语言文本字符集很大坏字符规则大概率能一把跳过很长的距离BM 的优势会非常明显。反过来如果模式串和文本都是单一字符重复比如用aaaaaaaa在aaaaaaaaaaaaaaaaaaaa里搜索BM 的好后缀表和坏字符表都发挥不出跳跃能力这时 KMP 反而是更稳的选择。我在实际处理日志关键词过滤时做过一次粗略对比文本大小 50MB模式串长度 5 到 20 个字符不等BM 的平均匹配耗时大约是朴素匹配的几十分之一比 KMP 也快一倍多。这非常符合 BM 的理论预期模式串越长每次失配跨越的距离越大总比较次数就越低。如果你用的是 JDK可以留意一下String.indexOf(String)的源码实现。现代 JDK 对单字符搜索做了一些优化对多字符搜索也已经引入了类似 BM 的启发式跳跃原理和本文讲的基本一致。很多语言的标准库也都在底层混用了 BM 思想的变体比如 Horspool 算法就是 BM 的简化版只保留坏字符规则。因此理解 BM 不只是为了应付一道算法题它真的能帮你读懂标准库的源码逻辑。6. 调 BM 时我踩过的 5 个坑写第一版 BM 时我自信满满结果在边界测试上连续翻车。这里把最重要的几个坑整理出来希望能帮你省掉排查时间。第一个坑坏字符表初始化成 0。很多简洁版代码把数组初始化为 0模式串里没有出现的字符也默认返回 0位移可能变成负数然后被保底逻辑吞掉看起来没死循环实际上搜索会不停重复比较同一个位置性能极差。一定要初始化成 -1因为 -1 才能让位移变成j 1正确跳过失配字符。第二个坑好后缀表构建时忘记检查“失配字符不能相同”。这个坑最隐蔽因为大部分测试都能过只有恰好遇到“移动后失配位置的新字符和原字符相同”的特殊模式才会漏匹配。我排查了很久才发现加上这个判断后之前偶尔漏掉的重叠匹配就恢复了。第三个坑失配位置 j 减到 -1 时L m - 1 - j会算出 m但好后缀表的 gs[m] 和 gs[0] 语义完全不同。gs[0] 表示一个都没匹配就失配这时候应该用坏字符表gs[m] 表示整个串都匹配成功应该独立处理。我把这两者混用过结果在重叠匹配场景里出现死循环。第四个坑只处理 char 不处理 Unicode 码点。Java 的 char 是 UTF-16 编码单元超出 BMP 的 emoji 或生僻字会拆成两个 char。如果你直接用 char 建表会匹配到半个字符结果完全错误。正确做法是先把模式串和文本都转成codePoint数组或者明确声明只支持 BMP 字符集。第五个坑流式分段搜索时丢边界。读取大文件时经常按行或按块读取如果模式串恰好跨越两个块边界就会漏匹配。我推荐在分块读取时保留前一块末尾的m - 1个字符作为重叠区等下一块来了再合并匹配。这个策略说起来简单但调试时经常因为少保留一个字符而翻车。如果你在实现中遇到搜索位置指数越界优先检查主循环的停止条件是不是i n - m很多实现写成了i n模式串贴近文本末尾时会访问越界。这个条件在朴素匹配里也容易写错但在 BM 里因为 i 推进很快越界概率更高。7. 写在最后我的实验手记BM 算法是我觉得“学起来难、用起来爽”的字符串算法典型代表。第一次手写建成两张表的时候公式推导让人头皮发麻但真正跑通大文件搜索并且看到耗时骤降后你会觉得前面死磕的每一分钟都值。我个人建议如果你打算把 BM 用到正式项目里按这样的顺序推进先用本文的暴力校验法建好后缀表保证逻辑正确再逐步替换成线性构建算法最后补上 Galil 优化把最坏复杂度压到线性。后面如果遇到多关键词同时搜索的场景BM 反而不适合应该转向 Aho-Corasick 自动机这类多模式算法。但多模式算法的内部匹配本质上也在利用“失败跳转”的启发式思想学懂了 BM 再看 AC 自动机会轻松很多。希望这篇文章能帮你在字符串匹配这条路上迈过最难的一道坎。