算法——Boyer-Moore算法

引言

在字符串匹配算法中，Boyer-Moore算法以其高效性和巧妙的设计而著称。它广泛用于文本搜索、编译器词法分析、信息检索等领域。本文将详细解读Boyer-Moore算法的原理、步骤，并通过实践案例展示其应用。

Boyer-Moore算法简介

Boyer-Moore算法是一种高效的字符串匹配算法，由Robert S. Boyer和J Strother Moore于1977年提出。该算法的核心思想是通过预处理模式串，利用字符比较的不匹配信息来跳过尽可能多的目标字符，从而快速定位可能的匹配位置，减少比较次数。

Boyer-Moore算法的基本原理

Boyer-Moore算法主要依赖于两个策略来减少比较的次数：坏字符规则（Bad Character Rule）和好后缀规则（Good Suffix Rule）。

坏字符规则：

当字符不匹配时，算法查找文本串中当前比较字符在模式串中出现的最后位置。
如果该字符在模式串中存在，模式串可以移动到该字符的位置；如果不存在，则模式串向右移动到文本串的下一个字符位置。

好后缀规则：

当部分模式串与文本串匹配后，如果发生不匹配，算法利用已匹配的后缀信息来移动模式串。
具体来说，算法查找已匹配后缀在模式串中的位置，或找到与已匹配后缀相同的部分，并进行相应的移动。

这两种规则相结合，使得Boyer-Moore算法能够在进行字符比较时，尽量减少不必要的比较。

Boyer-Moore算法的步骤

构建坏字符表：

创建一个表来记录每个字符在模式串中最后出现的位置。如果字符不在模式串中，则记录为-1。

构建好后缀表：

创建一个表来记录模式串中每个后缀的匹配信息，以便在匹配失败时调整模式串的位置。

匹配过程：

从模式串的末尾开始与文本串进行比较。
如果出现匹配，继续向左比较；如果出现不匹配，根据坏字符表或好后缀表移动模式串。

Boyer-Moore算法的Java实现

以下是Boyer-Moore算法的Java实现示例：

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

public class BoyerMooreAlgorithm {

    // 构建坏字符表
    private Map<Character, Integer> buildBadCharTable(String pattern) {
        Map<Character, Integer> badCharTable = new HashMap<>();
        int m = pattern.length();
        for (int i = 0; i < m; i++) {
            badCharTable.put(pattern.charAt(i), i);
        }
        return badCharTable;
    }

    // 构建好后缀表
    private int[] buildGoodSuffixTable(String pattern) {
        int m = pattern.length();
        int[] goodSuffixTable = new int[m + 1];
        int lastPrefixPosition = m; // 记录上一个前缀的位置

        // 初始化好后缀表
        for (int i = m; i >= 0; i--) {
            if (isPrefix(pattern, i)) {
                lastPrefixPosition = i;
            }
            goodSuffixTable[m - i] = lastPrefixPosition - i + (lastPrefixPosition == m ? 1 : 0);
        }

        // 计算好后缀的位置
        for (int i = 0; i < m - 1; i++) {
            int len = m - 1 - i;
            goodSuffixTable[len] = Math.min(goodSuffixTable[len], goodSuffixTable[m - 1 - i]);
        }

        return goodSuffixTable;
    }

    // 检查字符串是否为前缀
    private boolean isPrefix(String pattern, int p) {
        int m = pattern.length();
        for (int i = p, j = 0; i < m; i++, j++) {
            if (pattern.charAt(i) != pattern.charAt(j)) {
                return false;
            }
        }
        return true;
    }

    // Boyer-Moore字符串匹配算法
    public void boyerMoore(String text, String pattern) {
        Map<Character, Integer> badCharTable = buildBadCharTable(pattern);
        int[] goodSuffixTable = buildGoodSuffixTable(pattern);
        int n = text.length();
        int m = pattern.length();
        int i = 0; // 文本串的指针

        while (i <= n - m) {
            int j = m - 1; // 模式串的指针
            while (j >= 0 && text.charAt(i + j) == pattern.charAt(j)) {
                j--; // 如果匹配，继续向左比较
            }

            if (j < 0) {
                System.out.println("Pattern found at index: " + i);
                // 根据好后缀规则移动模式串
                i += (i + m < n) ? goodSuffixTable[0] : 1;
            } else {
                // 根据坏字符规则移动模式串
                i += Math.max(goodSuffixTable[j], j - badCharTable.getOrDefault(text.charAt(i + j), -1));
            }
        }
    }

    public static void main(String[] args) {
        BoyerMooreAlgorithm boyerMoore = new BoyerMooreAlgorithm();
        String text = "ABAAABCDABABCDAB";
        String pattern = "ABCD";
        boyerMoore.boyerMoore(text, pattern); // 在文本中查找模式串
    }
}