面试必备——BM字符串查找算法

写在前面

字符串的一种基本操作是子字符串查找：给定一端长度为N的文本字符串text和一个长度为M(M<N)的模式字符串pattern，在文本字符串中查找和该模式字符串相同的子字符串。在这互联网时代，字符串查找的需求在很多情景都需要，如在文本编辑器或浏览器查找某个单词、在通信内容中截取感兴趣的模式文本等等。

子字符串查找最简单的实现肯定是暴力查找：

public static int search(String text, String pattern) {
    int N = text.length();
    int M = pattern.length();
    for (int i = 0; i < N-M; i++) {
        int j;
        for (j = 0; j < M; j++) {
            if (text.charAt(i+j) != pattern.charAt(j))
                break;
        }
        if (j == M) return i;
    }

    return -1;
}

可以看到，暴力查找的最坏时间复杂度为O(N*M)，实际应用中往往文本字符串很长（成万上亿个字符），而模式字符串很短，这样暴力算法的时间复杂度是无法接受的。

为了改进查找时间，人们发明了很多字符串查找算法，而今天的主角BM算法（Bob Boyer和J Strother Moore发明，简称BM算法）就是其中的一种。

---

正文

不同于暴力查找算法的逐个字符对比，BM算法充分使用预处理模式字符串的信息来尽可能跳过更多的字符。在暴力算法中，比较一个字符串都是从首字母开始，逐个比较下去。一旦发现有不同的字符，就需要从头开始进行下一次比较，就需要将字串中的所有字符一一比较。BM算法的核心思路在于，文本字符串从左到右检索，模式字符串从右到左检索，当模式字符串的一个字符pattern[j]和文本字符串的字符text[i+j]不匹配时，那么在模式字符串中查找字符text[i+j]是否存在索引k，使得pattern[k] == text[i+j]，k若存在，k应该为满足条件的最右索引。此时存在三种情景：

• 情景1：若pattern不存在索引k(0 <= K < M)，使得pattern[k] == text[i+j]，那么text[i, i+j]不可能跟pattern匹配，那么i向右平移j+1。如图1所示。
• 情景2：若pattern存在索引k(0 <= K < M)，使得pattern[k] == text[i+j]，此时又有两种子情景：
  • 情景2.1：k < j，把text[i+j]对齐pattern[k]，也即把i向右平移j-k。如图2所示。
  • 情景2.2：k > j，显然i不能减少，那么把i加1。如图3所示。

图1 情景1 图2 情景2.1 图3 情景2.2

通过这种字符的移动方式来代替逐个比较，正是BM算法的高效的关键所在！那么我们怎么知道文本字符串的字符是否存在于模式字符串中？对的，预处理。我们在查找前，先建立一张包含文本字符串的所有字符的字母表，这张表中记录着字母表中的每个字符在模式字符串中出现的最靠右的索引，如果在字符在模式字符串中不存在，那么值为-1。

有了这张表，我们在查找时就可以高效的移动i。构建这张表很简单：

// 构建right数组
int R = 256; // 字母表大小，这里用ASCII字母表举例
int[] right = new int[R]; // 记录字母表中的每个字符在模式字符串中出现的最右的索引
for (int i = 0;  i < R; i++)
    right[i] = -1;
for (int j = 0; j < M; j++)
    right[pattern.charAt(j)] = j;

构建好表，我们只需要按上面分析的情景，出现字符不匹配时，通过表，把i向右平移到具体位置即可。BM完整算法实现如下：

public static int search(String text, String pattern) {
    int N = text.length();
    int M = pattern.length();

    // 构建right数组
    int R = 256; // 字母表大小
    int[] right = new int[R]; // 记录字母表中的每个字符在模式字符串中出现的最右的索引
    for (int i = 0;  i < R; i++)
        right[i] = -1;
    for (int j = 0; j < M; j++)
        right[pattern.charAt(j)] = j;

    int skip;
    for (int i = 0; i <= N-M; i+=skip) {
        skip = 0;
        for (int j = M-1; j >= 0; j--) {
            if (pattern.charAt(j) != text.charAt(i+j)) { // 不匹配的情况
                skip = j - right[text.charAt(i + j)]; // 这里包括情景1和情景2.1，如果情景1，right[text.charAt(i + j)]为-1
                if (skip < 1) skip = 1; // 情景2.2
                break;
            }
        }
        if (skip == 0) return i; // 匹配成功
    }
    return -1; // 未找到匹配
}

由于不匹配的情况属于大多数，所以一般情况下，BM算法的时间复杂度为O(N/M)，是线性级别的！可以说是非常高效了。但它需要额外的空间字母表大小R，所以BM算法是以空间换时间的。

至此，BM字符串查找算法已经分析完了，其实算是一种比较简单的算法，学习起来很快就能搞懂～

---

写在最后

参考

1. 《算法：第四版》

相关阅读

面试必备——KMP字符串查找算法