Boyer-Moore算法是经典的高效字符串匹配算法，通过预处理模式串构建坏字符表与好后缀表，实现大幅跳跃跳过不可能匹配的位置。本文用Java完整实现BM算法，讲解两种启发式规则的构建与协同工作原理。
算法核心思想
BM算法从模式串末尾向前比较。当不匹配时，利用两种启发式规则决定模式串右移距离：
– 坏字符规则：根据文本中不匹配的字符在模式串中的位置决定跳跃
– 好后缀规则：根据已匹配的后缀在模式串中的其他出现位置决定跳跃
取两者较大值作为实际跳跃距离。
public class BoyerMoore {
private final String pattern;
private final int[] badChar; // 坏字符表
private final int[] goodSuffix; // 好后缀表
public BoyerMoore(String pattern) {
this.pattern = pattern;
this.badChar = buildBadCharTable(pattern);
this.goodSuffix = buildGoodSuffixTable(pattern);
}
坏字符表构建
// 坏字符表：记录每个字符在模式串中最右出现位置
// 大小256覆盖ASCII字符集
static int[] buildBadCharTable(String pattern) {
int[] table = new int[256];
// 初始化为-1表示未出现
for (int i = 0; i < 256; i++) table[i] = -1;
for (int i = 0; i < pattern.length(); i++) {
table[pattern.charAt(i)] = i; // 记录最右位置
}
return table;
}
// 坏字符跳跃距离：若字符不在模式串中，跳跃m；否则跳跃 max(1, j - lastPos)
int badCharShift(char c, int j) {
int lastPos = badChar[c];
// j为当前不匹配位置（从右数）
return Math.max(1, j - lastPos);
}
好后缀表构建
// 好后缀表：当后缀已匹配但前面不匹配时，模式串应右移多少
static int[] buildGoodSuffixTable(String pattern) {
int m = pattern.length();
int[] suffix = new int[m]; // suffix[i]表示以i结尾的后缀与模式串后缀的最长匹配长度
int[] gs = new int[m]; // 好后缀跳跃表
// 计算suffix数组
suffix[m - 1] = m;
for (int i = m - 2; i >= 0; i--) {
int j = i;
while (j >= 0 && pattern.charAt(j) == pattern.charAt(m - 1 - i + j)) {
j--;
}
suffix[i] = i - j;
}
// 情况1：好后缀在模式串中有其他完整出现
for (int i = 0; i < m; i++) gs[i] = m;
int j = 0;
for (int i = m - 1; i >= 0; i--) {
if (suffix[i] == i + 1) {
for (; j < m - 1 - i; j++) {
if (gs[j] == m) gs[j] = m - 1 - i;
}
}
}
// 情况2：好后缀的后缀是模式串的前缀
for (int i = 0; i <= m - 2; i++) {
gs[m - 1 - suffix[i]] = m - 1 - i;
}
return gs;
}
完整搜索算法
// BM字符串匹配：返回所有匹配起始位置
public java.util.List<Integer> search(String text) {
java.util.List<Integer> matches = new java.util.ArrayList<>();
int n = text.length();
int m = pattern.length();
if (m == 0 || n < m) return matches;
int i = 0; // text中的对齐位置
while (i <= n - m) {
int j = m - 1; // 从模式串末尾开始比较
// 从右向左比较
while (j >= 0 && pattern.charAt(j) == text.charAt(i + j)) {
j--;
}
if (j < 0) {
// 完全匹配
matches.add(i);
// 继续搜索：使用好后缀规则移动
i += goodSuffix[0];
} else {
// 不匹配发生在位置j
char bad = text.charAt(i + j);
int bcShift = badCharShift(bad, j);
int gsShift = goodSuffix[j];
// 取两种规则的最大跳跃值
i += Math.max(bcShift, gsShift);
}
}
return matches;
}
主程序与性能对比
public static void main(String[] args) {
// 测试用例1：英文文本
String text = "ABAAABCDABCABCABCDABCDABAAABCD";
String pattern = "ABCD";
BoyerMoore bm = new BoyerMoore(pattern);
System.out.println("文本: " + text);
System.out.println("模式: " + pattern);
System.out.println("匹配位置: " + bm.search(text));
// 测试用例2：长文本性能对比
StringBuilder longText = new StringBuilder();
for (int i = 0; i < 1000000; i++) {
longText.append((char) ('a' + (i % 26)));
}
String lt = longText.toString();
String pat = "xyzabc";
// BM算法
long t1 = System.currentTimeMillis();
BoyerMoore bm2 = new BoyerMoore(pat);
java.util.List<Integer> bmResult = bm2.search(lt);
long t2 = System.currentTimeMillis();
System.out.println("\nBM搜索耗时: " + (t2 - t1) + "ms, 匹配数: " + bmResult.size());
// KMP算法对比
t1 = System.currentTimeMillis();
java.util.List<Integer> kmpResult = kmpSearch(lt, pat);
t2 = System.currentTimeMillis();
System.out.println("KMP搜索耗时: " + (t2 - t1) + "ms, 匹配数: " + kmpResult.size());
// 暴力算法对比
t1 = System.currentTimeMillis();
java.util.List<Integer> bruteResult = bruteSearch(lt, pat);
t2 = System.currentTimeMillis();
System.out.println("暴力搜索耗时: " + (t2 - t1) + "ms, 匹配数: " + bruteResult.size());
}
// KMP算法实现（用于对比）
static java.util.List<Integer> kmpSearch(String text, String pattern) {
java.util.List<Integer> result = new java.util.ArrayList<>();
int n = text.length(), m = pattern.length();
int[] lps = new int[m];
int len = 0;
for (int i = 1; i < m; i++) {
while (len > 0 && pattern.charAt(i) != pattern.charAt(len)) len = lps[len - 1];
if (pattern.charAt(i) == pattern.charAt(len)) lps[i] = ++len;
}
int i = 0, j = 0;
while (i < n) {
if (text.charAt(i) == pattern.charAt(j)) { i++; j++; }
if (j == m) { result.add(i - j); j = lps[j - 1]; }
else if (i < n && text.charAt(i) != pattern.charAt(j)) {
if (j > 0) j = lps[j - 1]; else i++;
}
}
return result;
}
static java.util.List<Integer> bruteSearch(String text, String pattern) {
java.util.List<Integer> result = new java.util.ArrayList<>();
int n = text.length(), m = pattern.length();
for (int i = 0; i <= n - m; i++) {
int j = 0;
while (j < m && text.charAt(i + j) == pattern.charAt(j)) j++;
if (j == m) result.add(i);
}
return result;
}
}
算法分析
预处理复杂度：坏字符表 O(m + |Σ|)，好后缀表 O(m)，其中 m 为模式串长度，Σ 为字符集。
搜索复杂度：最坏 O(n * m)，但在实际文本（尤其是自然语言）中，平均接近 O(n/m)，因为每次不匹配常能跳跃多个字符。在随机文本中，BM通常显著快于KMP。
空间复杂度：坏字符表 O(|Σ|)，好后缀表 O(m)。
