BM算法

Boyer-Moore字符串搜索算法,简称BM算法,是一种非常高效的字符串搜索算法。1977年,德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了这种算法

我们平常所用的编辑器 Ctrl+F 搜索一般都用此算法

该算法从后往前匹配,并引入 坏字符规则(Bad Character Heuristic)好后缀规则(Good Suffix heuristic)

假设字符串为HERE IS A SIMPLE EXAMPLE,搜索词为 EXAMPLE

HERE IS A SIMPLE EXAMPLE
EXAMPLE

先匹配最后一个字符,匹配失败,此时S为坏字符,然后从 EXAMPL 里搜索最后一次出现S的位置,没有出现,那么跳过所有

HERE IS A SIMPLE EXAMPLE
       EXAMPLE

继续匹配最后一个字符,匹配失败,P 为坏字符,然后从 EXAMPL 里搜索最后一次出现 P 的位置,然后往后移动使其对齐

HERE IS A SIMPLE EXAMPLE
         EXAMPLE
HERE IS A SIMPLE EXAMPLE
         EXAMPLE

对齐后从后往前匹配,匹配了 MPLE,被称为好后缀,I 匹配失败,在 EX 找 I 最后一次出现的位置,未出现,跳过 len(EXAMPLE) - len(MPLE) = 7 - 4 = 3 位

HERE IS A SIMPLE EXAMPLE
            EXAMPLE

从后往前匹配,匹配失败,查找 X 最后一次出现的位置,移动并对齐

HERE IS A SIMPLE EXAMPLE
                 EXAMPLE

从后往前匹配,匹配成功


linux c例子

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h>

#define dl_max(x,y) ((x) > (y) ? (x) : (y))

void bad_ch_heuristic(char *pat, int n, int *bc)
{
    int i;

    for (i = 0; i < 256; i++)
        bc[i] = -1;

    for (i = 0; i < n; i++)
        bc[pat[i]] = i;
}

void bm_search(char *pat, char *txt)
{
    int m,n,i,j,s;

    m = strlen(pat);
    n = strlen(txt);

    int bc[256];

    bad_ch_heuristic(pat, m, bc);

    s = 0;
    /*
      j 为 pat 索引
      s 为 txt 开始匹配索引
    */
    while (s <= (n-m)) {
        j = m - 1;

        //从后往前开始比对
        while (j >= 0 && pat[j] == txt[s+j])
            j--;

        if (j < 0) {
            //匹配成功
            printf("found at index %d\n", s);
            s += m;
        } else {
            s += dl_max(1, j - bc[txt[s+j]]);
        }
    }
}

int main(int argc, char **argv) 
{
    if (argc != 3)
        return 0;

    char *pat = argv[2];
    char *txt = argv[1];

    bm_search(pat, txt);

    return 0;
}


参考:

geeksforgeeks-bm算法

维基-bm算法

上一篇: KMP算法
下一篇: Sunday算法
作者邮箱: 203328517@qq.com