每日算法 — 使用java实现BM字符串搜索：Boyer-Moore坏字符与好后缀规则

引言

Boyer-Moore（BM）算法是字符串匹配领域中最快的实用算法之一。与从左向右逐字符比较的朴素方法不同，BM算法从模式串的末尾开始比较，并利用预处理的坏字符规则（Bad Character Rule）和好后缀规则（Good Suffix Rule）实现大步长跳跃。在最优情况下，BM算法的时间复杂度可达O(n/m)，其中n为文本长度，m为模式串长度。本文将用Java完整实现BM算法，包括两种启发式规则的预处理与联合决策逻辑。

核心思想

假设文本为T，模式串为P，从位置i开始对齐：

1. 从右向左比较：先比较P[m-1]与T[i+m-1]，若匹配则继续向左
2. 坏字符规则：当T[i+j] ≠ P[j]时，若T[i+j]在P中出现过，则将P中该字符最右出现位置对齐到T[i+j]；若未出现，则直接将P移到该字符右侧
3. 好后缀规则：当已匹配后缀P[j+1..m-1] = T[i+j+1..i+m-1]但P[j] ≠ T[i+j]时，查找P中是否有相同后缀可以重新对齐

实际位移取两种规则计算值的最大值，确保安全跳过不可能匹配的位置。

Java实现

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Boyer-Moore字符串匹配算法完整实现
 * 包含坏字符规则与好后缀规则
 */
public class BoyerMooreSearch {

    private final String pattern;
    private final int m; // 模式串长度
    private final Map<Character, Integer> badCharTable; // 坏字符表
    private final int[] goodSuffixTable; // 好后缀表

    /**
     * 构造函数：预处理模式串
     */
    public BoyerMooreSearch(String pattern) {
        this.pattern = pattern;
        this.m = pattern.length();
        this.badCharTable = buildBadCharTable();
        this.goodSuffixTable = buildGoodSuffixTable();
    }

    /**
     * 构建坏字符表
     * 记录每个字符在模式串中最右出现的位置（从0开始）
     * 若字符不在模式串中，默认为-1
     */
    private Map<Character, Integer> buildBadCharTable() {
        Map<Character, Integer> table = new HashMap<>();
        for (int i = 0; i < m; i++) {
            table.put(pattern.charAt(i), i); // 后出现的覆盖先出现的，保留最右位置
        }
        return table;
    }

    /**
     * 查询坏字符规则给出的位移量
     * @param badChar 文本中不匹配的字符
     * @param badPos  该字符在模式串中的位置（从0开始）
     * @return 模式串应向右移动的位数
     */
    private int getBadCharShift(char badChar, int badPos) {
        Integer rightmostPos = badCharTable.get(badChar);
        if (rightmostPos == null) {
            // 字符不在模式串中，直接将模式串移到该字符右侧
            return badPos + 1;
        }
        // 最右出现位置在badPos左侧：直接对齐
        // 最右出现位置在badPos右侧或等于：避免回溯，移动1位
        int shift = badPos - rightmostPos;
        return shift > 0 ? shift : 1;
    }

    /**
     * 构建好后缀表
     * goodSuffixTable[i] 表示当不匹配发生在位置i时（即P[0..i-1]已匹配），
     * 模式串需要向右移动的距离
     * 
     * 核心逻辑：
     * 1. 情况A：P中存在子串与好后缀匹配，将最右侧的匹配子串对齐
     * 2. 情况B：P的前缀与好后缀的后缀匹配，将前缀对齐
     * 3. 情况C：都不满足，移动m位
     */
    private int[] buildGoodSuffixTable() {
        int[] table = new int[m];
        int[] suffix = computeSuffixLengths(); // suffix[i] = 以i结尾的最长匹配后缀长度

        // 初始化：情况C，全部设为m
        Arrays.fill(table, m);

        // 情况B：处理P的前缀与好后缀后缀匹配的情况
        // 从右向左扫描，找到前缀匹配
        int j = 0;
        for (int i = m - 1; i >= 0; i--) {
            if (suffix[i] == i + 1) { // P[0..i]是某个后缀的前缀匹配
                for (; j < m - 1 - i; j++) {
                    if (table[j] == m) {
                        table[j] = m - 1 - i;
                    }
                }
            }
        }

        // 情况A：处理内部子串匹配
        for (int i = 0; i < m - 1; i++) {
            table[m - 1 - suffix[i]] = m - 1 - i;
        }

        return table;
    }

    /**
     * 计算suffix数组
     * suffix[i] = 满足 P[i-s+1..i] == P[m-s..m-1] 的最大s值
     * 即：以位置i结尾的子串，与模式串后缀匹配的最大长度
     */
    private int[] computeSuffixLengths() {
        int[] suffix = new int[m];
        suffix[m - 1] = m; // 最后一个字符，整个串都是后缀

        int g = m - 1; // 上一次失配的位置
        int f = 0;     // 当前匹配子串的起始位置

        for (int i = m - 2; i >= 0; i--) {
            if (i > g && suffix[i + m - 1 - f] < i - g) {
                // 利用之前计算的结果
                suffix[i] = suffix[i + m - 1 - f];
            } else {
                // 直接扩展比较
                if (i < g) g = i;
                f = i;
                while (g >= 0 && pattern.charAt(g) == pattern.charAt(g + m - 1 - f)) {
                    g--;
                }
                suffix[i] = f - g;
            }
        }

        return suffix;
    }

    /**
     * 查询好后缀规则给出的位移量
     * @param badPos 不匹配发生的位置
     * @return 位移量
     */
    private int getGoodSuffixShift(int badPos) {
        return goodSuffixTable[badPos];
    }

    /**
     * 在文本中搜索模式串，返回首次匹配的位置（从0开始），未找到返回-1
     */
    public int search(String text) {
        int n = text.length();
        if (m == 0) return 0;
        if (m > n) return -1;

        int i = 0; // 模式串在文本中的起始位置

        while (i <= n - m) {
            int j = m - 1; // 从模式串末尾开始比较

            // 从右向左匹配
            while (j >= 0 && pattern.charAt(j) == text.charAt(i + j)) {
                j--;
            }

            if (j < 0) {
                // 完全匹配
                return i;
            }

            // 失配发生在位置j
            char badChar = text.charAt(i + j);
            int badCharShift = getBadCharShift(badChar, j);
            int goodSuffixShift = getGoodSuffixShift(j);

            // 取两种规则的最大值（更安全的跳跃）
            int shift = Math.max(badCharShift, goodSuffixShift);
            i += shift;
        }

        return -1;
    }

    /**
     * 在文本中搜索所有匹配位置
     */
    public java.util.List<Integer> searchAll(String text) {
        java.util.List<Integer> results = new java.util.ArrayList<>();
        int n = text.length();
        if (m == 0 || m > n) return results;

        int i = 0;
        while (i <= n - m) {
            int j = m - 1;
            while (j >= 0 && pattern.charAt(j) == text.charAt(i + j)) {
                j--;
            }

            if (j < 0) {
                results.add(i);
                // 继续搜索：使用好后缀规则移动
                i += goodSuffixTable[0];
            } else {
                char badChar = text.charAt(i + j);
                int shift = Math.max(getBadCharShift(badChar, j), getGoodSuffixShift(j));
                i += shift;
            }
        }

        return results;
    }

    /**
     * 打印预处理表（调试用）
     */
    public void printTables() {
        System.out.println("模式串: " + pattern);
        System.out.println("坏字符表:");
        for (Map.Entry<Character, Integer> entry : badCharTable.entrySet()) {
            System.out.printf("  '%c' -> %d%n", entry.getKey(), entry.getValue());
        }
        System.out.println("好后缀表 (位置->位移):");
        for (int i = 0; i < m; i++) {
            System.out.printf("  失配在P[%d]: 移动%d%n", i, goodSuffixTable[i]);
        }
    }

    /**
     * 与朴素算法对比性能
     */
    public static void benchmark() {
        // 构造大文本
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 100000; i++) {
            sb.append("ABCDEFGHIJKLMNOPQRSTUVWXYZ");
        }
        sb.append("PATTERN_MATCH_END");
        String text = sb.toString();
        String pattern = "PATTERN_MATCH_END";

        // BM算法
        BoyerMooreSearch bm = new BoyerMooreSearch(pattern);
        long start = System.nanoTime();
        int bmResult = bm.search(text);
        long bmTime = System.nanoTime() - start;

        // 朴素算法
        start = System.nanoTime();
        int naiveResult = text.indexOf(pattern);
        long naiveTime = System.nanoTime() - start;

        System.out.printf("文本长度: %d, 模式串长度: %d%n", text.length(), pattern.length());
        System.out.printf("BM算法:   结果=%d, 耗时=%.3fms%n", bmResult, bmTime / 1e6);
        System.out.printf("朴素算法: 结果=%d, 耗时=%.3fms%n", naiveResult, naiveTime / 1e6);
        System.out.printf("加速比: %.1fx%n", (double) naiveTime / bmTime);
    }

    public static void main(String[] args) {
        // 基础功能演示
        String text = "ABAAABCDABCABCDABCDABDE";
        String pattern = "ABCABCD";

        BoyerMooreSearch bm = new BoyerMooreSearch(pattern);
        bm.printTables();

        int pos = bm.search(text);
        System.out.printf("%n在\"%s\"中搜索\"%s\": 首次匹配位置=%d%n", text, pattern, pos);

        java.util.List<Integer> allPos = bm.searchAll(text);
        System.out.println("所有匹配位置: " + allPos);

        // 性能测试
        System.out.println("\n=== 性能对比 ===");
        benchmark();
    }
}

复杂度分析

• 预处理：
• 坏字符表：O(m × |Σ|) 时间，O(|Σ|) 空间（|Σ|为字符集大小）
• 好后缀表：O(m) 时间，O(m) 空间
• 搜索：
• 最坏情况：O(nm)（如文本为”AAAAA”，模式为”AAAB”）
• 平均情况：O(n/m) 次比较，实际运行极快
• 最优情况：O(n/m) 当字符集较大时

算法变体与选择

Boyer-Moore算法是grep等文本搜索工具的核心基础，理解其双启发式规则的设计思想，对掌握字符串算法的高阶技巧至关重要。