BM算法详解

来源

在没有BM算法时，其原始算法是从后往前进行匹配，需要两层循环，判断以某个字符为结尾的子串是否和模式串相等，这种算法也称作暴搜；

贴上代码：

void BLS(string s, string p) {
    int s_len = s.size(), p_len = p.size();
    int j = 0, i = 0;
    
    while (j <= s_len - p_len) {
        for (i = p_len - 1; i >= 0 && p[i] == s[i + j]; --i) {}
        if (i < 0) {
            cout << "match: " << i + j + 1 << endl;
            j += p_len;
        }
        else
            j++;
    }
}

算法的思想还是比较容易理解的，i和j分别指的是，模式串中已经匹配的位数，模式串相对于原串移动的位数；

移动规则

算法包含了两个重要的内容，分别是好后缀和坏字符的规则；

坏字符：当模式串和原串的字符并不匹配时，原串中的字符就称为坏字符；
好后缀：模式串和原串的字符相等时所有的字符串，比如ABCD和BCD，那么它的好后缀则包括第一次匹配的D，和第二次匹配的CD，还有第三次的BCD；

例子：

BM算法的向右移动模式串的距离就是取坏字符和好后缀算法得到的最大值；

这两个内容分别拥有着几条规则，需要注意：

坏字符

坏字符没出现在模式串中，这时可以把模式串移动到坏字符的下一个位置，继续比较；

比如说，ABC和D，其中D和A对齐，因为不匹配，所以D会移动到和B对齐；
坏字符出现在模式串中，这时可以把模式串中第一个出现（从后往前数第一个出现，也就是从前往后数，最靠右出现的）的坏字符和原串的坏字符对齐；

比如说，BCCBCAD和AAD，假如其中AAD和BCC对齐，发现D和C无法匹配，移动到和BCA匹配，此时同样不匹配，但是A存在于模式串中，所以移动到模式串中坏字符出现的上一次位置，也就是向后移一位，和CAD对齐；

当首次比较就无法匹配时，那么肯定是运用坏字符规则，因为并不存在好后缀；

所以我们发现坏字符的移动规则公式为：

后移位数＝坏字符的位置－模式串中的上一次出现位置

那用代码表示则是

void preBmBc(string x, vector<int>& bmBc) {
    int i = 0;
    int len = (int)x.size();
    // 全部更新为自己的长度
    for (i = 0; i < ASIZE; ++i) {
        bmBc[i] = len;
    }

    // 计算字符串中每个字符距离字符串尾部的长度
    for (i = 0; i < x.size() - 1; ++i) {
        bmBc[x[i]] = len - i - 1;
    }
}

首先应该知道的是，bmBc存储的是坏字符出现的位置距离模式串末尾的最大长度；

前一个循环用来处理第一种规则，因为遇见不匹配时，直接移动模式串的长度；

后一个循环处理第二种规则，需要注意的是，因为要保证最靠右原则，所以要从头开始循环，从而使得当遇见相同的字符，后者可以将前者进行覆盖。

好后缀

模式串中有子串匹配上好后缀，此时移动模式串，让子串和好后缀对齐即可，如果超过一个子串匹配上好后缀，则选择最靠左边的子串对齐；
模式串中没有子串匹配上后缀，接着寻找模式串中的一个和好后缀（子串）相等的最长前缀，并让该前缀和好后缀对齐即可；
模式串中没有子串匹配上好后缀，并且在模式串中找不到和好后缀（子串）相等的最长前缀，此时，直接移动模式到好后缀的下一个字符；

综上，好后缀的规则：

后移位数＝好后缀的位置－模式串中的上一次出现的位置

用代码表示为：

我们先看suffix数组的计算

// 计算以i为边界，与模式串后缀匹配的最大长度（区间的概念）
void suffix(string x, vector<int>& suff) {
//    int len = x.size();
//    int f = 0, q = len - 1, i;
//
//    // 设置最后一个为自己的长度
//    suff[len-1] = len;
//
//    // 从倒数第二个开始，
//    for (i =  len - 2; i >= 0; --i) {
//        if (i > q && suff[i + len - 1 - f] < i - q) {
//            suff[i] = suff[i + len - 1 + f];
//        }
//        else {
//            if (i < q) {
//                q = i;
//            }
//            f = i;
//            while (q >= 0 && x[q] == x[len - 1 - f + q]) {
//                --q;
//            }
//
//            suff[i] = f - q;
//        }
//    }
    
    int len = (int)x.size();
    int q;
    for (int i = len - 2; i >= 0; --i) {
        q = i;
        while (q >= 0 && x[q] == x[len-1-i+q]) {
            --q;
        }
        suff[i] = i - q;
    }
    
}

为什么要计算suffix数组呢，因为我们需要通过suffix去计算bmGs。

suffix数组的定义为：以i为边界，与模式串后缀匹配的最大长度；有可能是和整个后缀相等的子串又或者只是最长前缀又或者都不匹配，它们都会有不同的长度，都不匹配自然是模式串的长度，因为要移动到好后缀的下一个字符。

接着看怎么计算bmGs数组，代码：

// 好后缀算法的预处理
/*
 有三种情况
 1.模式串中有子串匹配上好后缀
 2.模式串中没有子串匹配上好后缀，但找到一个最大前缀
 3.模式串中没有子串匹配上好后缀，但找不到一个最大前缀


 3种情况获得的bmGs[i]值比较

 3 > 2 > 1

 为了保证其值越来越小

 所以按顺序处理3->2->1情况
 */
void preBmGs(string s, vector<int>& bmGs) {

    int i, j;
    int len = (int)s.size();

    vector<int> suff(len, 0);

    suffix(s, suff);

    //全部初始为自己的长度，处理第三种情况
    for (i = 0; i < len; ++i) {
        bmGs[i] = len;
    }

    // 处理第二种情况
    for (i = len - 1; i >= 0; --i) {
        if (suff[i] == i+1) { // 找到合适位置
            for (j = 0; j < len-1; ++j) {
                if (bmGs[j] == len) { // 保证每个位置至多只能被修改一次
                    bmGs[j] = len - 1 - i;
                }
            }
        }
    }

    // 处理第一种情况，顺序是从前到后
    for (i = 0; i < len - 1; ++i) {
        bmGs[len - 1- suff[i]] = len - 1 - i;
    }

}

bmGs[i]数组表示存在好后缀时，模式串应该移动的距离，i表示坏字符的位置；

先看第三种情况

很容易理解，自然是模式串的长度；

再看第二种情况

为什么会让suffix[i] = i + 1，因为suffix存储的是i位置字符的最长匹配长度，所以其代表的是j...i的长度，只有当表达式成立的时候，说明其是个前缀；

找到了以后，从后往前扫，可以保证最长，因为从i位置往前的前缀是匹配的，那么其移动的距离自然是len - 1 - i；

其加了个判断，避免后面再遇到前缀时，不再允许更改；

再看第一种情况

因为是子串，不再是前缀，不用加上判断，况且前者已经处理过；

len - 1- suff[i]，因为suffix[i]的长度和好后缀的长度相同，所以得到的是好后缀的前一个字符；

i表示的是以i开始往前数的子串，从该位置要移动到最后一个位置，自然距离就是len - 1 - i

总函数

BM算法的核心在于其移动规则，接下来看最后的处理部分；

void BM(string pattern, string text) {
    int i, j;
    int m = (int)pattern.size(), n = (int)text.size();
    vector<int> bmGs(m);
    vector<int> bmBc(ASIZE);

    // 处理好后缀算法
    preBmGs(pattern, bmGs);
    // 处理坏字符算法
    preBmBc(pattern, bmBc);

    j = 0;

    while (j <= n - m) {
        // 模式串向左边移动
        for (i = m - 1; i >= 0 && pattern[i] == text[i + j]; --i);

        // 给定字符串向右边移动
        if (i < 0) {
            cout << j << endl;
            j += m; // 移动到模式串的下一个位置
        }
        else {
            if (text[i+j] == 'P') {
                cout << "find" << endl;
            }
            // 取移动位数的最大值向右移动，前者好后缀，向右移动，后者坏字符，向左移动
            //cout << text[i+j] << bmBc[text[i+j]] << endl;
            j += max(bmGs[i], bmBc[text[i+j]] - m + 1 + i);
        }
    }
}

其中 j 表示模式串和原串的距离；

循环中那个for循环，计算着匹配距离，从模式串的长度开始，如果 i 为－1，自然其和模式串是相等的，如果不相等，则按照移动规则来移动（取最大值哦）。

实例

了解一下BM算法是怎么运作的：

初始化
首次出现坏字符

从后往前进行匹配，我们发现S和E并不匹配，而且是一开始比较就无法匹配上，则整个字符串肯定无法匹配；S则称为坏字符（即原串中无法匹配的字符），因为S并没出现在模式串中，故我们只能使用第一种规则，即将模式串移到S的下一位对齐；
坏字符存在模式串中

移动到模式串中上一次出现的位置；
开始匹配

相等，开始匹配；
存在前缀，和好后缀（子串）相等

发现不存在子串和好后缀相等，但存在前缀E，移动到和好后缀的E对齐；
坏字符存在模式串中

发现P和E不相等，P存在模式串中，运用坏字符规则；
相等匹配完成

完成!

文章参考以下内容：

阮一峰

博客圆