Boyer-Moore字符串查找算法

发表于 | 分类于

这是一种类似于KMP但是更高效一点、也更简单一些的字符串查找算法，大体的思路是从右往左扫描，例如在txt = ABCBCDCDE中查找模式串pat = BCD，

1
2
ABCBCDCDE
BCD

从右往左，第一个比较的字符是 C 和 D ，不匹配，C 在 BCD 里出现的所有位置中最靠右是 1，那么 BCD 右移 1 位，比较 B 和 D ，

1
2
ABCBCDCDE
 BCD

不匹配，B 在 BCD里出现的所有位置中最靠右是 0，那么BCD右移 2 位，

1
2
ABCBCDCDE
   BCD

匹配成功，当然例子有些简单，看完以下的具体规则后，就会消除你所有的顾虑 = =！
具体的规则如下：（ i 是 txt 中的游标，j 是 pat 中的游标）

1. 如果失配字符不在 pat 中，那么 pat 右移 j+1 个位置，也就是 i += j+1 继续比较。这条应该是浅显易懂，不懂得在纸上画一下就知道了。

2. 如果失配字符在 pat 中，那么 pat 右移，使得适配字符与 pat 中该字符出现的所有位置中最右的那个对齐，即右移 j - x 即 i += j - x ，x 即是最右位置。

3. 如果以上两条不能使 i 增大，i += 1。

以上第 2 条的 x 可以通过预处理来提前计算好，计算的代码如下：

1
2
3
4
5
6
int right[256];
memset(right, -1, sizeof(int) * 256);// 初始化为-1

for (int k = 0; k < strlen(pat); ++k) {
    right[pat[k]] = k;
}

查找代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int skip = 0;
for (int i = 0; i < strlen(txt) - strlen(pat); i += skip) {
    skip = 0;
    for (int j = (int)strlen(pat)-1; j >= 0; --j) {
        if (txt[i+j] != pat[j]) { // 字符匹配失败
            skip = j - right[pat[j]];
            if (skip < 1) { // i 无法增大
                skip += 1;
            }
            break;
        }
    }
    if (skip == 0) { // 全部匹配成功
        return i;
    }
}

PS：可以根据KMP的思路，优化一下，即已经匹配过的，是不是有相同的串。

参考：《算法》第四版

显示 Gitment 评论