BM字符匹配算法

前言

��       字符匹配在我们的电脑有非常广泛的应该，例如记事本的查找以及搜索引擎的匹配等等，KMP算法也是一种匹配算法，但实际上它并不那么高效，大多数应用还是会选择BM（Boyer-Moore）算法，实际上BM算法会比 KMP 算法可以快很多。

        （在学BM算法前建议先看懂KMP算法的原理）

        BM算法是由Bob Boyer和J Strother Moore于1977年提出的一种更快的字符串匹配算法，其核心思想是利用模式串中的已知信息，尽可能地跳过一些不必要的比较。BM算法分为两个步骤：预处理和匹配。预处理阶段主要是构建一个坏字符规则和好后缀规则的数据结构。坏字符规则用于处理模式串中出现频率极低的字符；好后缀规则用于处理模式串中重复出现的后缀。在匹配阶段，根据预处理阶段构建的数据结构，快速跳过一些不必要的比较。

BM算法原理

下面用moore的例子来说明原理：

假定我们要搜索的模式串为“EXAMPLE”，主串为“HERE IS A SIMPLE EXAMPLE”。

在匹配过程中，我们先将首部对齐，从尾部开始比较，如果说尾部最后一个不一致，那说明前面的七个字符就不是我们要找的结果，但是很多人可能会想到如果 从第二位开始到第八位 是我们想要匹配的字符呢？别着急往下看，在这个例子里，S和E不匹配，我们就称这个字符为坏字符，同时我们可以发现S不存在于我们模式串EXAMPLE里，所以我们直接跳过这7个字符也无所谓（这里可以用KMP来理解，仅理解，没有共同前后缀，所以直接跳过。

接下来，我们把字符串向前移动 7 位，继续进行比较

发现P与E不匹配，但是此时EXAMPLE中存在了相同的字符P，该怎么做呢？那我们只用把字符串移动到这两个P对齐，即向前移动 2 位

这时候我们可以得到，当我们尾部出现坏字符不匹配的情况时，它应该移动的位数

        后移位数=坏字符的位置-该字符在字符串中上一次出现的位置

例如 P是坏字符，它后移（6-4）=2位  （下标从1开始），那E为什么移动7位，它上一次出现的位置应该怎么算？对于字符中不存在的字符，它在字符串中上一次出现的位置设为-1，这样N-(-1)=N+1就刚好能跳过该字符并从该字符下一个开始匹配

这时再重新从尾部开始比较：

 

匹配则前移：

   

我们把尾部这些匹配的子字符串称为好后缀，注意MPLE、PLE、LE、E都是好后缀

再向前比较

I与A不匹配，根据坏字符方法，我们可以得到这样的结果：

但是貌似还有更好的方法，我们现在是知道I后面的MPLE是已经匹配了的，那么如果在我们的模式串中如果存在MPLE这样的前缀，我们就可以直接让该前缀和后缀匹配，跳过没必要的字符匹配例如假如我们的模式串是ABCDAB，得到的好后缀是AB、B，那么我们可以跳过AB直接匹配AB后的一个字符（参考KMP算法的最长公共前后缀），此时得到的好后缀的移动规则：

        后移位数=好后缀的位置-该好后缀在模式串中上一次出现的位置

那在上面的例子中，我们知道EXAMPLE中存在E，即后移位置=（6-0）=6（注意是上上一张图转移到下图）。根据坏字符移动规则能移动3位，根据好后缀移动规则能移动6位，BM算法就是移动两者中较大的一位。

后缀位置规则注意：

1、好后缀的位置是以最后一个字符的位置确定的，例如上例中MPLE、PLE、LE、E好后缀的位置都是 E 的位置 6，ABCDAB中的AB好后缀的位置是 5 。

2、如果好后缀只出现一次，位置为-1。(同上坏字符，此时没有最长公共前后缀）

3、如果好后缀有多个，则除了最长的那个好后缀，其他好后缀的上一次出现位置必须在头部。（同KMP的最长公共前后缀，去了解了就知道了）换个理解方式就是BABCDAB中DAB是好后缀，则它上一次出现的位置可以看成（DA）BABCDAB，即0的位置。

此时不匹配再后移，直到末尾匹配成功

总结规则：

坏字符：移动的位数 = 坏字符在模式串中的位置 - 坏字符在模式串中最右出现的位置

好后缀：移动的位数 = 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置

无论是好后缀还是坏字符，他们都与主串无关，只和搜索串有关系，那我们可以事先求出得到一个移动表格，需要时查表即可以大大提升效率。

单就BM算法的时间复杂度来说，最坏时间复杂度可以达到O(nm)，最好时间复杂度为O(n/m)，平均时间复杂度为O(n/m)。

代码实现

实现坏字符移动规则表：

vector get_bad_char_table(const string& pattern){    vector B_C_table(256,-1);//字符的范围为0~255，不存在的计为-1    for(int i=0;i= 0; i--)        for (int j = 0; j = 0; i--)    {        if (suffix[i] == i + 1)        {            for (int j = 0; j   
BM代码实现：
 
int BM_Search(string str,string pattern){    vector S=get_suffix_table(pattern);    vector GS=get_good_suffix_table(pattern,S);    vector BC=get_bad_char_table(pattern);    int m=str.size(),n=pattern.size();    int i = n - 1, j = n - 1;    int shift = 0;    int pos = n - 1;    while (shift + n - 1 = 0 && pattern[pos] == str[shift + pos]; pos--)            ;        if (pos == -1)            break;        else            shift += max(pos - BC[str[shift + pos]], GS[pos]);    }    return shift + n - 1