Boyer-Moore算法详解（Java语言实现高效字符串匹配）

为什么Boyer-Moore这么快？

Boyer-Moore算法在实际应用中通常比KMP等算法更快，尤其是在模式串较长、字符集较大的情况下。因为它每次可以跳过多个字符，而不是像暴力法那样逐个移动。最坏时间复杂度为O(mn)，但在实践中平均时间复杂度接近O(n/m)，其中n是文本长度，m是模式长度。

Java实现Boyer-Moore算法

下面我们用Java实现一个简化版的Boyer-Moore算法，仅使用坏字符规则（这是最常用且效果显著的部分）。完整的实现会同时使用坏字符和好后缀规则，但为了便于理解，我们先掌握核心思想。

public class BoyerMoore {    // 构建坏字符表    private static int[] buildBadCharTable(char[] pattern) {        int[] badChar = new int[256]; // 假设ASCII字符集        Arrays.fill(badChar, -1);                // 记录每个字符在pattern中最后一次出现的位置        for (int i = 0; i < pattern.length; i++) {            badChar[pattern[i]] = i;        }                return badChar;    }    // Boyer-Moore搜索主函数    public static int search(String text, String pattern) {        if (pattern.isEmpty()) return 0;                char[] txt = text.toCharArray();        char[] pat = pattern.toCharArray();                int n = txt.length;        int m = pat.length;                int[] badChar = buildBadCharTable(pat);                int shift = 0; // 当前模式串相对于文本的偏移量                while (shift <= n - m) {            int j = m - 1; // 从模式串末尾开始比较                        // 从右向左匹配            while (j >= 0 && pat[j] == txt[shift + j]) {                j--;            }                        if (j < 0) {                // 找到匹配                return shift;            } else {                // 使用坏字符规则计算移动距离                int badCharShift = j - badChar[txt[shift + j]];                shift += Math.max(1, badCharShift);            }        }                return -1; // 未找到    }    // 测试示例    public static void main(String[] args) {        String text = "HERE IS A SIMPLE EXAMPLE";        String pattern = "EXAMPLE";                int index = search(text, pattern);        if (index != -1) {            System.out.println("匹配位置: " + index);        } else {            System.out.println("未找到匹配");        }    }}

代码说明

1. buildBadCharTable 函数构建一个大小为256的数组（对应ASCII字符），记录每个字符在模式串中最后一次出现的位置。若未出现，则为-1。

2. 在 search 函数中，我们从模式串末尾开始比较。如果发现不匹配，就根据坏字符表计算应跳过的位数。

3. 移动距离不能小于1，否则会陷入死循环，因此使用 Math.max(1, badCharShift)。

总结

通过本教程，我们学习了Boyer-Moore算法的基本原理及其在Java语言中的实现。这种高效搜索方法在处理大文本时优势明显，是每一位程序员应掌握的重要字符串匹配技术。

虽然我们只实现了坏字符规则，但已经能显著提升性能。如果你希望进一步优化，可以尝试加入好后缀规则，这将使算法在更多场景下表现更佳。

掌握Boyer-Moore，让你的字符串搜索飞起来！