BM算法

最近在学习数据结构与算法，在字符串模式匹配的算法学习时，总结了一下知识点方便自己回顾与理解。
其他相关字符串匹配算法：
RK算法
KMP算法

BM算法思想：有模式串中不存在的字符，那么肯定不匹配，往后多移动几位，提高效率。

因此，BM算法就是借助这种规律，在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。

BM算法定义了两个规则，好后缀规则和坏字符规则，同时其匹配的顺序是按照模式串下标从大到小的顺序，即从后往前

利用好后缀和坏字符可以大大加快模式串的移动距离，不是简单的++j，而是j+=max

坏字符规则

情况1：字符没出现在模式串中，这时可以把模式串移动到坏字符的下一个字符，继续比较，如下图：

情况2：坏字符出现在模式串中，这时可以把模式串右边第一个出现的坏字符和主串的坏字符对齐

• 注意：如果坏字符在模式串中多次出现，取最靠”右“的，因为这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过。

我们可以用哈希表来存储坏字符在模式串中的最右边的位置：

void generateBadChar(string p,map<char,int> & badchar){
    int n = p.size();
    for (int i = 0; i < n; i++){
        //如果不再哈希表中，则说明是第一次出现
        if (badchar.find(p[i]) == badchar.end()){
            badchar.insert({p[i],i});
        }else{
        //如果出现在哈希表中，说明已经出现了，但是我们存储的是最靠右的哪个位置，因此更新
            badchar[p[i]] = i;
        }    
    }
}

由上我们可以推导出来一个规律：

设坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作 xi。如果不存在，我们把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi。

有时候在遇到坏字符匹配失败时，不但不会向后滑动模式串，还有可能倒退。

不过，单纯使用坏字符规则还是不够的。因为根据 si-xi 计算出来的移动位数，有可能是负数，比如主串是 cccccccccccc，模式串是 accc。不但不会向后滑动模式串，还有可能倒退，因为根据以上计算方式，si = 0 ,xi = 1, si - xi = -1。

所以，BM算法还需要用到**“好后缀规则”**。

但是在这之前，先把 BM 算法代码的大框架写好，先不考虑好后缀规则，仅用坏字符规则，并且不考虑 si-xi 计算得到的移动位数可能会出现负数的情况。因为出现负数的情况可以根据后面比较两种规则所得到结果进行去除。

//只根据坏字符规则进行的BM匹配
/*
@param s : 主串
@param p : 模式串
*/
int BM_Badchar(string s,string p){
    int lens = s.size();
    int lenp = p.size();
    map<char,int> badchar;
    getBadChar(p,badchar);
    //i：表示主串与模式串对齐的第一个字符 
    int i = 0,j;
    //i时第i+1此匹配结束的位置
    while (i < lens - lenp + 1){
        //从后往前的顺序匹配
        for(j = lenp - 1; j >= 0; j--){
            //匹配失败，直接退出循环，开始滑动模式串
            if (s[i+j] != p[j]){
                break;
            }
        }
        // j < 0匹配成功
        if (j < 0){
            return i;
        }
        //坏字符不在模式串中，直接模式串滑动j+1位
        if (badchar.find(s[i+j]) == badchar.end()){
            i = i + j + 1;;//等价于 i = i + (j - badchar[s[i+j]])，其中 badchar[s[i+j]] 为 -1
        }else{
        //坏字符在模式串中，滑动(j - badchar['x'])位数
            i = i + (j - badchar[s[i+j]]);
        }
    }
    return -1;
}

好后缀规则

当模式串滑动到图中的位置的时候，模式串和主串有 2 个字符是匹配的，倒数第 3 个字符发生了不匹配的情况。

我们把已经匹配的 bc 叫作好后缀，记作{u}。拿它在模式串中查找，如果找到了另一个跟{u}相匹配的子串{u * }，那我们就将模式串滑动到子串{u * }与主串中{u}对齐的位置。

如果在模式串中找不到另一个等于{u}的子串，我们就直接将模式串，滑动到主串中{u}的后面，因为之前的任何一次往后滑动，都没有匹配主串中{u}的情况。

不过，当模式串中不存在等于{u}的子串时，我们直接将模式串滑动到主串{u}的后面。这样可能会错过模式串和主串可以匹配的情况。

如果好后缀在模式串中不存在可匹配的子串，那在我们一步一步往后滑动模式串的过程中，只要主串中的{u}与模式串有重合，那肯定就无法完全匹配。但是当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候，并且重合的部分相等的时候，就有可能会存在完全匹配的情况。

所以，不仅要看好后缀是否在模式串中，还要判断好后缀的后缀子串是否与模式串的前缀子串相匹配的情况。，如果有，则从好后缀的后缀子串中，找一个最长的且和模式串的前缀子串匹配的 {v}，滑动至 {v} 对齐

根据上面的讲解我们可以知道在利用好后缀规则时，我们需要：

   1. 在模式串中，查找跟好后缀匹配的另一个子串；
   2. 找出好后缀的所有后缀子串 
   3. 找出模式串的所有前缀子串
   4. 找到好后缀中最长的能和模式串的前缀子串匹配的后缀子串

注意：好后缀的后缀子串，本身也是模式串的后缀子串（因为好后缀是已经匹配的部分)，所以我们可以利用这个在模式串中找到另外的对应匹配的字符，因此我们可以在模式串和主串正式匹配之前，通过预处理模式串，预先计算好模式串的每个后缀子串，对应的另一个可匹配子串的位置。

后缀子串：拿 bcab 来讲, 它的后缀子串如下表:

注意：因为后缀子串的最后一个字符的位置是固定的，下标为 m-1，我们只需要记录长度就可以了。通过长度，我们可以确定一个唯一的后缀子串。

引入 suffix 数组

假设我们在好后缀中的某个子串的长度为 k, 它在模式串中的子串中有相同的子串, 且起始位置为 i, 那么我们就记录 suffix[k] = i；如果不存在,我们就记录为 suffix[k] = -1.

引入 prefix 数组

除了 suffix 数组之外，我们还需要另外一个 bool 类型的 prefix 数组，来记录模式串的后缀子串(好后缀的后缀子串)是否能匹配模式串的前缀子串.（前缀子串的定义和后缀子串相似）

如何计算并填充这两个数组的值呢？

我们拿下标从 0 到 i 的子串（i 可以是 0 到 m-2）与整个模式串，求公共后缀子串。如果公共后缀子串的长度是 k，那我们就记录 suffix[k]=j（j 表示公共后缀子串的起始下标）。如果 j 等于 0，也就是说，公共后缀子串也是模式串的前缀子串，我们就记录 prefix[k]=true。

//计算suffix和prefix数组
/*
@param p : 模式串
*/
void generateGS(string p,vector<int> &suffix,vector<bool> & prefix){
    //suffix[k] = int(i)：表示好后缀的长度为k的好后缀子串，在除了此位置外的最右位置i
    //prefix[k] = bool : 表示是否存在长度为k的好后缀子串也是模式串的前缀字串
    int n = p.size();
    //k：后缀子串的长度
    int i,j,k;
    for (int i = 0; i < n-1; i++){
        j = i;
        k = 0;//从j位置开始寻找长度为k的公共后缀字串（每个位置都是从0开始寻找）
        while (j >= 0 && p[j] == p[n-1-k]){
            --j;
            ++k;//公共后缀子串长度(模式串尾部取k个出来，分别比较)
            suffix[k] = j+1;
            //相同后缀子串长度为k时，该子串在b[0,i]中的起始下标
            // (如果有多个相同长度的子串，被赋值覆盖，存靠右的)
        }
        //查找到模式串的头部了
        if (j == -1){
            prefix[k] = true;//如果公共后缀子串也是模式串的前缀子串
        }
    }
}

如何计算滑动位数：

假设好后缀的长度是 k。我们先拿好后缀，在 suffix 数组中查找其匹配的子串。如果 suffix[k]不等于 -1（-1 表示不存在匹配的子串），那我们就将模式串往后移动 j-suffix[k]+1 位（j 表示坏字符对应的模式串中的字符下标）。如果 suffix[k]等于 -1，表示模式串中不存在另一个跟好后缀匹配的子串片段。

好后缀的后缀子串 b[r, m-1]（其中，r 取值从 j+2 到 m-1）的长度 k=m-r，如果 prefix[k]等于 true，表示长度为 k 的后缀子串，有可匹配的前缀子串，这样我们可以把模式串后移 r 位。注意：好后缀是[j+1，m-1], 好后缀的子串肯定小于好后缀，就不能从j+1开始,从j+2开始

如果两条规则都没有找到可以匹配好后缀及其后缀子串的子串，我们就将整个模式串后移 m 位。

代码如下：

//根据坏字符位置j,suffix和prefix，求取移动的位数
/*
@param j : 坏字符位置
@param return : 模式串应该后移位数
*/
int moveByGS(int j,int lenp,vector<int> &suffix,vector<bool> &prefix){
    int k = lenp - j - 1;//好后缀长度
    //如果模式串中有好后缀，则直接计算后移位数
    if (suffix[k] != -1){
        return j - suffix[k] + 1;
    }
    //好后缀是[j+1，m-1], 好后缀的子串肯定小于好后缀，就不能从j+1开始,从j+2开始
    for(int r = j + 2; r < lenp; ++r){
        //lenp-r是好后缀的子串的长度，如果这个好后缀的子串是模式串的前缀子串
        if(prefix[lenp-r] == true)//lenp - r 等价于 m-1-r+1 = m-r = lenp-r
        //在上面没有找到相同的好后缀下，移动r位，对齐前缀到好后缀
            return r;
    }
    return lenp;//case3,都没有匹配的，移动lenp位（模式串长度） 
}

如何选择使用哪种规则

• 分别计算好后缀和坏字符规则往后滑动的位数，取大的，作为滑动位数（还可以避免负数,即反向滑动）

int BMMatching(string s,string p){
    int lens = s.size();
    int lenp = p.size();
    if (lens == 0 || lenp == 0){//存在空串，匹配失败
        return -1;
    }
    map<char,int> badchar;
    vector<int> suffix(lenp,-1);
    vector<bool> prefix(lenp,false);
    //根据坏字符规则计算badchar
    getBadChar(p,badchar);
    //计算suffix和prefix
    generateGS(p,suffix,prefix);
    //movelen1：根据坏字符规则求得的滑动位数
    //movelen2：根据好后最规则求得的滑动位数
    int i = 0,movelen1 = 0,movelen2 = 0,j;
    while (i < lens-lenp+1){
        for (j = lenp - 1; j >= 0; j--){
            if (s[i+j] != p[j]){//遇到坏字符
                break;
            }
        }
        if (j < 0){//匹配成功
            return i;
        }
        //坏字符不在模式串中，直接模式串滑动j+1位
        if (badchar.find(s[i+j]) == badchar.end()){
            movelen1 =  j + 1;;
        }else{
        //坏字符在模式串中，滑动(j - badchar['x'])位数
            movelen1 =  (j - badchar[s[i+j]]);
        }
        movelen2 = 0;
        if (j < lenp-1){//如果有好后缀
            movelen2 = moveByGS(j,lenp,suffix,prefix);
        }
        //选取滑动位数多的那一个
        i = i + max(movelen1,movelen2);
    }
    return -1;
}

性能分析

空间复杂度：

个算法用到了额外的 3 个数组（suffix 、prefix和哈希表badchar），其中 badchar的大小跟字符集大小有关，suffix 数组和 prefix 数组的大小跟模式串长度 m 有关。

因为好后缀和坏字符规则是独立的，如果我们运行的环境对内存要求苛刻，可以只使用好后缀规则，不使用坏字符规则，这样就可以避免 bcbadchar 数组过多的内存消耗。不过，单纯使用好后缀规则的 BM 算法效率就会下降一些了。

时间复杂度：

在极端情况下，预处理计算 suffix 数组、prefix 数组的性能会比较差。比如模式串是 aaaaaaa 这种包含很多重复的字符的模式串，预处理的时间复杂度就是 O(m^2)。当然，大部分情况下，时间复杂度不会这么差。

参考文章：王老师的《数据结构与算法之美》课程很棒！推荐学习！