boyer-moore算法从模式串末尾向左匹配，利用坏字符规则和好后缀规则跳过文本位置；工程中常仅实现坏字符规则，通过预处理构建坏字符表（记录各字符在模式中最右位置，未出现则为-1）来决定失配时的右移位数。
Boyer-Moore 算法核心思想
Boyer-Moore 不是从左到右逐个比对，而是从模式串（pattern）末尾开始向左匹配。一旦失配，它利用两个启发式规则跳过尽可能多的文本位置：坏字符规则（Bad Character Rule）和好后缀规则（Good Suffix Rule）。实际工程中常只实现坏字符规则，它已能显著提升平均性能（尤其模式较长时），且实现简洁、易理解、内存开销小。
Java 中实现坏字符规则版 Boyer-Moore
关键步骤是预处理模式串，构建一个“坏字符表”——记录每个字符在模式串中最后一次出现的位置（从右往左看）。若字符未出现，则记为 -1。匹配时，用该表决定每次失配后模式串应右移多少位。
以下是轻量、可直接运行的 Java 实现：
Java JDK 25 来自 OpenJDK 官方归档，版本为 JDK 25，本条下载地址已指向官方 Windows x64 zip 安装包直链，适合调试旧项目或兼容旧版 Java 运行环境。
// 返回 pattern 在 text 中首次出现的起始索引，未找到返回 -1
public static int boyerMooreSearch(String text, String pattern) {
if (pattern.isEmpty()) return 0;
if (text.length()
// 构建坏字符表：ASCII 字符范围足够覆盖常见场景
int[] badChar = new int[256];
Arrays.fill(badChar, -1);
for (int i = 0; i
badChar[pattern.charAt(i)] = i;
}
int s = 0; // 模式串在 text 中的起始偏移
while (s
int j = pattern.length() - 1;
// 从右向左匹配
while (j >= 0 && pattern.charAt(j) == text.charAt(s + j)) {
j--;
}
if (j
return s; // 完全匹配
} else {
// 计算移动距离：max(1, j - 坏字符在 pattern 中最右位置)
int shift = j - badChar[text.charAt(s + j)];
s += Math.max(1, shift);
}
}
return -1;
}
使用示例与注意事项
- 调用方式简单：
int pos = boyerMooreSearch("abacababc", "ababc");→ 返回4 - 坏字符表用
int[256]支持 ASCII；如需 Unicode 全量支持，可改用Map<character integer></character>，但会略慢且占内存 - 该实现不处理空 pattern 的边界（已显式返回 0），也不做 null 检查——生产环境建议前置校验
- 注意：
s + j是当前失配位置，text.charAt(s + j)即“坏字符”，其在 pattern 中最后出现位置由表给出
与 Java 内置方法对比
String.indexOf() 在 OpenJDK 中实际采用的是优化过的 Two-Way 算法（用于长模式）或简单循环（短模式），并非 Boyer-Moore。它在大多数日常场景下已足够快，且经过高度 JIT 优化。自己实现 BM 主要用于学习算法原理、特定场景（如固定长模式+海量文本扫描）、或嵌入式/受限环境。除非有明确性能瓶颈和实测优势，否则不建议替代 indexOf。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
