每日算法 — 使用java实现BM算法：坏字符跳转与好后缀规则的高效字符串匹配

引言

在文本处理、搜索引擎、DNA序列分析等领域，字符串匹配是最基础也最频繁的操作之一。Boyer-Moore（BM）算法是实践中最高效的单模式匹配算法之一，其平均时间复杂度接近O(n/m)，其中n为文本长度，m为模式串长度。本文将深入讲解BM算法的两大核心启发式策略——坏字符规则与好后缀规则，并提供完整的Java实现。

核心算法概述

1. 坏字符规则（Bad Character Heuristic）

BM算法从右向左比较模式串与文本。当发生不匹配时，如果文本中的这个”坏字符”在模式串中不存在，则可以将模式串直接右移m位；如果存在，则将其对齐到模式串中最右侧出现的位置。

2. 好后缀规则（Good Suffix Heuristic）

当模式串的后缀部分已经匹配成功（称为”好后缀”），但前面的字符不匹配时，如果在模式串的其他位置也存在相同的后缀，则可以将模式串滑动到该位置对齐。此外，如果好后缀的某个后缀同时也是模式串的前缀，也可以利用这一信息。

Java完整实现

import java.util.*;

/**
 * Boyer-Moore字符串匹配算法完整实现
 * 包含：坏字符规则、好后缀规则、预处理表构建
 */
public class BoyerMooreAlgorithm {

    private final String pattern;
    private final int patternLength;
    private final int ALPHABET_SIZE = 256; // ASCII字符集大小

    // 坏字符表：记录每个字符在模式串中最右出现的位置
    private int[] badCharTable;

    // 好后缀表：记录好后缀对应的滑动距离
    private int[] goodSuffixTable;

    public BoyerMooreAlgorithm(String pattern) {
        this.pattern = pattern;
        this.patternLength = pattern.length();
        this.badCharTable = new int[ALPHABET_SIZE];
        this.goodSuffixTable = new int[patternLength];

        preprocessBadChar();
        preprocessGoodSuffix();
    }

    /**
     * 预处理坏字符表
     * badCharTable[c] = 字符c在模式串中最右出现的位置索引
     * 如果字符不在模式串中，值为-1
     * 时间复杂度：O(m)，m为模式串长度
     */
    private void preprocessBadChar() {
        // 初始化为-1，表示字符未在模式串中出现
        Arrays.fill(badCharTable, -1);

        // 填充每个字符在模式串中最右出现的位置
        for (int i = 0; i < patternLength; i++) {
            badCharTable[pattern.charAt(i)] = i;
        }
    }

    /**
     * 预处理好后缀表
     * 好后缀规则是BM算法的精髓，分为两种情况：
     * 1. 模式串中存在另一个与好后缀完全匹配的子串
     * 2. 好后缀的某个后缀是模式串的前缀
     * 时间复杂度：O(m)
     */
    private void preprocessGoodSuffix() {
        // suffix[i]表示以位置i为结尾的后缀与模式串后缀的最长匹配长度
        int[] suffix = new int[patternLength];
        Arrays.fill(suffix, -1);

        // 计算suffix数组
        // 从倒数第二个字符开始，自右向左计算
        suffix[patternLength - 1] = patternLength; // 最后一个字符的后缀就是整个模式串

        for (int i = patternLength - 2, g = patternLength - 1; i >= 0; i--) {
            // g是上一个匹配成功的起始位置的前一个位置
            if (i > g && suffix[i + patternLength - 1 - g] < i - g) {
                // 如果当前位置在上一个匹配区间内部，且suffix值已知
                suffix[i] = suffix[i + patternLength - 1 - g];
            } else {
                // 重新计算匹配长度
                if (i < g) {
                    g = i;
                }
                int j = i >= 0 ? i : 0;
                // 从位置g向前比较
                while (g >= 0 && pattern.charAt(g) == pattern.charAt(g + patternLength - 1 - j)) {
                    g--;
                }
                suffix[j] = j - g;
            }
        }

        // 情况1：模式串中存在另一个与好后缀匹配的子串
        // 初始化所有位置为patternLength，即最坏情况下滑动m位
        Arrays.fill(goodSuffixTable, patternLength);

        // 情况2：好后缀的某个后缀也是模式串的前缀
        // 从右向左找到第一个suffix[i] == i+1的位置
        int j = 0;
        for (int i = patternLength - 1; i >= 0; i--) {
            if (suffix[i] == i + 1) {
                // 从位置0到j都满足前缀条件
                for (; j < patternLength - 1 - i; j++) {
                    if (goodSuffixTable[j] == patternLength) {
                        goodSuffixTable[j] = patternLength - 1 - i;
                    }
                }
            }
        }

        // 情况1填充：存在匹配的子串
        for (int i = 0; i <= patternLength - 2; i++) {
            goodSuffixTable[patternLength - 1 - suffix[i]] = patternLength - 1 - i;
        }
    }

    /**
     * 使用BM算法在文本中搜索模式串
     * 返回所有匹配起始位置的列表
     * 
     * @param text 待搜索的文本
     * @return 所有匹配位置的列表
     */
    public List<Integer> search(String text) {
        List<Integer> matches = new ArrayList<>();
        if (text == null || text.length() < patternLength) {
            return matches;
        }

        int textLength = text.length();
        int shift = 0; // 当前模式串在文本中的起始位置

        while (shift <= textLength - patternLength) {
            int j = patternLength - 1; // 从模式串末尾开始比较

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

            if (j < 0) {
                // 完全匹配成功
                matches.add(shift);
                // 使用好后缀规则滑动到下一个可能匹配的位置
                shift += goodSuffixTable[0];
            } else {
                // 在位置j发生不匹配
                char badChar = text.charAt(shift + j);

                // 坏字符规则计算的滑动距离
                int badCharShift = j - badCharTable[badChar];
                if (badCharShift < 1) {
                    badCharShift = 1; // 至少滑动1位，避免死循环
                }

                // 好后缀规则计算的滑动距离
                int goodSuffixShift = goodSuffixTable[j];

                // 取两者最大值，确保不遗漏任何匹配
                shift += Math.max(badCharShift, goodSuffixShift);
            }
        }

        return matches;
    }

    /**
     * 打印预处理表，用于调试和理解算法
     */
    public void printPreprocessTables() {
        System.out.println("=== 坏字符表（部分） ===");
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            if (badCharTable[i] != -1) {
                System.out.printf("  '%c' -> 最右位置 %d%n", (char)i, badCharTable[i]);
            }
        }

        System.out.println("\n=== 好后缀表 ===");
        for (int i = 0; i < patternLength; i++) {
            System.out.printf("  位置 %d -> 滑动 %d%n", i, goodSuffixTable[i]);
        }
    }

    /**
     * 基准测试：对比BM算法与朴素算法的性能
     */
    public static void benchmark() {
        // 构造大规模测试文本
        StringBuilder sb = new StringBuilder();
        Random random = new Random(42);
        for (int i = 0; i < 1000000; i++) {
            sb.append((char)('a' + random.nextInt(26)));
        }
        String text = sb.toString();
        String pattern = "algorithm";

        // 预热
        BoyerMooreAlgorithm bm = new BoyerMooreAlgorithm(pattern);
        bm.search(text);

        // BM算法计时
        long start = System.nanoTime();
        List<Integer> bmResult = bm.search(text);
        long bmTime = System.nanoTime() - start;

        // 朴素算法计时
        start = System.nanoTime();
        List<Integer> naiveResult = naiveSearch(text, pattern);
        long naiveTime = System.nanoTime() - start;

        System.out.println("=== 性能对比 ===");
        System.out.printf("文本长度: %d, 模式串长度: %d%n", text.length(), pattern.length());
        System.out.printf("BM算法: %d matches, time = %.2f ms%n", 
                         bmResult.size(), bmTime / 1_000_000.0);
        System.out.printf("朴素算法: %d matches, time = %.2f ms%n", 
                         naiveResult.size(), naiveTime / 1_000_000.0);
        System.out.printf("加速比: %.2fx%n", (double)naiveTime / bmTime);
    }

    /**
     * 朴素字符串匹配算法（暴力法）
     */
    private static List<Integer> naiveSearch(String text, String pattern) {
        List<Integer> matches = new ArrayList<>();
        int n = text.length();
        int 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) {
                matches.add(i);
            }
        }
        return matches;
    }

    public static void main(String[] args) {
        // 示例1：基础演示
        String text = "ABAAABCDABCABCDABCDABD";
        String pattern = "ABCABCD";

        System.out.println("=== BM算法基础演示 ===");
        System.out.println("文本: " + text);
        System.out.println("模式: " + pattern);

        BoyerMooreAlgorithm bm = new BoyerMooreAlgorithm(pattern);
        bm.printPreprocessTables();

        List<Integer> matches = bm.search(text);
        System.out.println("\n匹配位置: " + matches);

        // 示例2：大规模性能测试
        System.out.println("\n");
        benchmark();

        // 示例3：DNA序列匹配
        System.out.println("\n=== DNA序列匹配示例 ===");
        String dna = "ATCGATCGATCGATCGATCGATCGATCGATCG";
        String gene = "ATCGATCG";
        BoyerMooreAlgorithm dnaBM = new BoyerMooreAlgorithm(gene);
        List<Integer> dnaMatches = dnaBM.search(dna);
        System.out.println("DNA序列: " + dna);
        System.out.println("基因片段: " + gene);
        System.out.println("匹配位置: " + dnaMatches);
    }
}

/**
 * 扩展实现：BM算法在文件搜索中的应用
 */
class FilePatternSearcher {

    /**
     * 在多行文本中搜索模式，返回匹配的行号和列号
     */
    public static List<int[]> searchInLines(String[] lines, String pattern) {
        List<int[]> results = new ArrayList<>();
        BoyerMooreAlgorithm bm = new BoyerMooreAlgorithm(pattern);

        for (int lineNo = 0; lineNo < lines.length; lineNo++) {
            List<Integer> matches = bm.search(lines[lineNo]);
            for (int pos : matches) {
                results.add(new int[]{lineNo + 1, pos + 1}); // 1-based indexing
            }
        }
        return results;
    }

    public static void main(String[] args) {
        String[] codeLines = {
            "public class HelloWorld {",
            "    public static void main(String[] args) {",
            "        System.out.println(\"Hello, World!\");",
            "        String pattern = \"Hello\";",
            "        System.out.println(pattern);",
            "    }",
            "}"
        };

        List<int[]> results = searchInLines(codeLines, "Hello");
        System.out.println("在代码中搜索 'Hello':");
        for (int[] pos : results) {
            System.out.printf("  第%d行, 第%d列%n", pos[0], pos[1]);
        }
    }
}

算法复杂度分析

关键知识点总结

1. 从右向左比较：BM算法最大的创新点在于改变了比较方向。当模式串较长且字符集较大时，从右向左比较使得每次不匹配都能获得更大的滑动距离。

2. 坏字符规则：通过预处理方式串中每个字符的最右位置，发生不匹配时可以立即计算出安全的滑动距离。该规则对ASCII文本（如英文）特别有效。

3. 好后缀规则：通过分析模式串自身的结构，利用已匹配的后缀信息来决定滑动距离。该规则在处理DNA序列（字符集仅4种）时尤为重要。

4. 双规则取最大：实际实现中同时应用坏字符和好后缀两个规则，取两者计算出的滑动距离的最大值，确保安全性（不漏匹配）的同时最大化效率。

5. 实际应用：BM算法及其变种（如Horspool、Sunday算法）广泛应用于GNU grep、Vim搜索等工具中，是工业界字符串匹配的事实标准之一。