企业官网建设流程全解析

如果你平时写代码，经常需要在长文本里找一个短字符串，大概率用过系统自带的indexOf或者朴素的双层循环。真正让我开始认真研究字符串算法，是因为一次日志分析任务：几 GB 的文本里反复检索上百个关键词，朴素匹配慢到让人怀疑人生。后来接触了 BM 算法（Boyer-Moore），用一个大文件实测，搜索速度肉眼可见提升。这个字符串算法在文本编辑器、查找替换、内容过滤、病毒特征码匹配等场景里都被大量使用，核心思路却非常简单：匹配时从右往左看，失配时用“坏字符”和“好后缀”两条规则尽量大步跳跃，而不是老老实实一格一格挪。

这篇文章不打算只堆公式，我会把两张预处理表从原理到代码完整拆一遍，再附一份可以直接复跑 Java 实现，最后聊聊我自己调 BM 时踩过的一些坑。不管你是刚接触字符串匹配的新手，还是想深入源码级优化的老手，应该都能在这里找到点有用的东西。

1. 从暴力匹配到 BM：为什么匹配时要从右往左看

先说清楚 BM 解决了什么问题。朴素的字符串匹配思路很简单：把模式串放在文本开头，从左到右逐位比较，失配就整体右移一格，直到文本末尾。这种方案最坏情况下比较次数是模式串长度乘以文本长度，也就是 O(n*m)。文本一长，比如几十 MB 的日志文件，再叠加几十上百个关键词，耗时就会被放大得非常恐怖。

KMP 算法是另一种经典方案，它利用模式串自身的前后缀信息，失配时避免从头再比，达到线性复杂度 O(n+m)。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[i+j]。模式串里如果存在字符c，取其最后一次出现的位置k，那么模式串可以安全右移j - k位；如果模式串里根本没有c，则右移j + 1位，让失配字符整体落在窗口左侧之外。

为什么取“最后一次出现”而不是“第一次出现”？因为我们必须保证移动后，不会把一个可能匹配的位置错过。如果模式串中c出现多次，移动太多会让最后一次出现的c滑到失配字符左边，那个位置可能是匹配起点；而如果移动太少，又没必要。只有让“离失配位置最近的那次出现”来对齐文本失配字符，才是不多不少的安全界限。

看上图的教科书经典例子：文本"HERE IS A SIMPLE EXAMPLE"，模式串"EXAMPLE"，开始比较text[6]，这个位置是空格，模式串里没有空格，于是直接右移 7 位。再比较新对齐位置，文本还是空格？不对，因为此时失配可能是另一个字符，但同样可以大步跳跃。这个规则让模式串经常“跳”掉大段明显不可能匹配的文本。

坏字符表的构建只需要扫一遍模式串，记录每个字符最后一次出现的下标即可。因为要加速 lookup，通常用一个长度为字符集大小的数组；如果字符集是 ASCII，256 大小的数组就够了；处理一般 Javachar，用 65536 大小；工程上如果处理 Unicode 码点，就得用HashMap<Integer, 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 List<Integer> searchAll(String text, String pattern) { List<Integer> 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 在大多数真实场景里明显更快，原因在于它平均跳得快。这里贴一张我自己的对比表，供你参考：

这里有一个容易混淆的点：KMP 的最坏复杂度 O(n+m) 是数学上更漂亮的上界，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 自动机会轻松很多。希望这篇文章能帮你在字符串匹配这条路上迈过最难的一道坎。