Java中BM(Boyer-Moore)算法的图解与实现

前言

本文主要介绍在Java中实现BM算法。BM算法是一种高效的模式匹配算法，其核心思想是，对于模式串的每个字符，在匹配串中寻找该字符时，优先从模式串的尾部开始匹配，以减少匹配步骤。本文将详细介绍BM算法的流程，并提供两个示例以帮助读者更好地理解该算法。

算法流程

1. 计算字符偏移量表
2. 字符集假设有m个字符
3. 索引表（下表从0开始）b数组，b[i]表示模式串中，左侧第i个字符（即从左往右第i+1个）在模式串中最后一次出现的位置，如果不存在则为-1
4. sbc数组，sbc[i]表示在模式串中字符i的偏移量，即可以向右移动sbc[i]使得模式串中字符i与匹配串的当前匹配位置对齐
5. 匹配模式串
6. 从匹配串的开头开始，以步长i+j为递增的方式扫描匹配串，i表示匹配串的第一位，j表示模式串的第一位
7. 对于每一次的匹配，从模式串的尾部开始逐个检测字符，如果遇到不匹配的字符跳过，直到找到相同的字符为止
8. 如果匹配完整个模式串，则返回当前匹配的起始位置；否则，根据偏移量表移动模式串，进行下一次匹配

代码实现

public class BoyerMoore {
    private static int[] buildBC(char[] pattern) {
        int[] bc = new int[256];
        for (int i = 0; i < bc.length; i++) {
            bc[i] = -1;
        }
        for (int i = 0; i < pattern.length; i++) {
            bc[pattern[i]] = i;
        }
        return bc;
    }

    private static int[] buildSBC(char[] pattern) {
        int[] sbc = new int[256];
        for (int i = 0; i < sbc.length; i++) {
            sbc[i] = pattern.length;
        }
        for (int i = 0; i < pattern.length - 1; i++) {
            sbc[pattern[i]] = pattern.length - i - 1;
        }
        return sbc;
    }

    public static int bm(char[] text, char[] pattern) {
        int[] bc = buildBC(pattern);
        int[] sbc = buildSBC(pattern);
        int i = 0;
        while (i <= text.length - pattern.length) {
            int j = pattern.length - 1;
            while (j >= 0 && pattern[j] == text[i + j]) {
                j--;
            }
            if (j < 0) {
                return i;
            } else {
                i += Math.max(sbc[text[i + j]] - pattern.length + j + 1, bc[text[i + j]]);
            }
        }
        return -1;
    }
}

示例说明

示例一

文本串：ABCBABACABCBACABCBAC
模式串：CBAC

char[] text = "ABCBABACABCBACABCBAC".toCharArray();
char[] pattern = "CBAC".toCharArray();
int index = BoyerMoore.bm(text, pattern);
System.out.println(index); // 输出 11

运行结果：该示例中匹配到了第一个模式串CBAC，其起始位置为11，可以发现BM算法对于长文本和短模式具有很高的匹配效率。

示例二

文本串：ADFHdjkakoksjdfaDHDSD
模式串：ab

char[] text = "ADFHdjkakoksjdfaDHDSD".toCharArray();
char[] pattern = "ab".toCharArray();
int index = BoyerMoore.bm(text, pattern);
System.out.println(index); // 输出 -1

运行结果：该示例中匹配模式串失败，返回-1。需要注意的是，模式串不区分大小写，所以示例中的"AB"和"ab"实际上是等效的，匹配结果将一致。

结论

通过以上的流程介绍和实例说明，我们可以看到BM算法的匹配效率很高，特别适合处理长文本和短模式的匹配问题。此外，通过实现该算法，也可以加深理解算法的核心思想，对于日后的算法学习和应用都会有所帮助。