字符串匹配：BM

核心思想

把模式串和主串的匹配过程，看做模式串在主串中不停地往后滑动。当遇到不匹配的字符时，BF和RK算法的做法是，模式串往后滑动一位，然后从模式串的第一个字符开始重新匹配。

主串中的某个字符，在模式串中不存在，模式串向后滑动的时候，只要该字符与模式串有重合，肯定无法匹配，可以一次性把模式串往后多滑动几位，跳过一些肯定不会匹配的情况，以此来减少不必要的字符比较，提高匹配的效率。

原理分析

BM算法包含两部分，分别是坏字符规则和好后缀规则。

坏字符规则

BM算法的匹配顺序是按照模式串下标从大到小的顺序，倒着匹配的。
从模式串的末尾往前倒着匹配，当发现某个字符没法匹配的时候，把这个没有匹配的字符叫做坏字符(主串中的字符)。

1. 拿坏字符在模式串中查找，发现模式串中并不存在这个字符，也就是说，主串中该字符与模式串中的任何字符都不可能匹配。这个时候，可以将模式串直接滑动到主串中该字符后面的位置，再从模式串的末尾字符开始比较。

2. 坏字符在模式串中是存在的。可以将模式串往后移动到坏字符与之匹配的字符对齐的地方，然后再从模式串的末尾字符开始，重新匹配。

当发生不匹配的时候，把坏字符对应的模式串中的字符下标记作si。
如果坏字符在模式串中存在，把这个坏字符在模式串中的下标记作xi。如果不存在，把xi记作-1。模式串往后移动的位数就等于si-xi。(这里的下标，都是字符在模式串的下标。)
如果坏字符在模式串中里多处出现，在计算xi的时候，选择最靠后的那个，不会让模式串滑动过多，导致本来可能匹配的请款被滑动略过。

利用坏字符规则，BM算法在最好情况下的时间复杂度为O(n/m)。

单纯使用坏字符规则，根据si-xi计算出来的移动位数，有可能是负数。不但不会向后滑动模式串，还有可能倒退。

好后缀规则

把已经匹配的字符叫做好后缀，记作{u}。拿它在模式串中查找，如果找到了另一个跟{u}相匹配的子串{u^*}，就将模式串滑动到子串{u^*}与主串中{u}对齐的位置。
如果在模式串中找不到另一个等于{u}的子串，就直接将模式串滑动到主串中{u}的后面。(之前的任何一次往后滑动，都不会有匹配主串中{u}的情况。)

当模式串中不存在等于{u}的子串时（好后缀在模式串中不存在可匹配的子串），直接将模式串滑动到主串{u}的后面，太过头。尽管在模式串中没有另外一个相匹配的子串{u^*}，在一步步往后滑动模式串的过程中，只要主串中的{u}与模式串有重合，那肯定就无法完全匹配。但当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候({u}可能是多个字符)，并且重合的部分相等，就有可能存在完全匹配的情况。

不仅要看好后缀在模式串中，是否有另一个匹配的子串，还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。
所谓某个字符串s的后缀子串，就是最后一个字符跟s对齐的子串。
所谓前缀子串，就是其实字符跟s对齐的子串。
从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，然后将模式串滑动到他们重合的位置。

综合

档模式串和主串中的某个字符不匹配的时候，可以分别计算好后缀和坏字符往后滑动的位数，然后去两个数中最大的，作为模式串往后滑动的位数。可以避免，值根据坏字符规则，计算得到的往后滑动的位数，有可能是负数的情况。

代码实现

坏字符

拿坏字符在模式串中顺序遍历查找比较低效，将模式串中的每个字符及其下标都存到散列表中。
假设字符串的字符集不大，每个字符长度是1字节，用大小为256的数组，记录每个字符在模式串中出现的位置。数组的下标对应字符的ASCII码值，数组中存储这个字符在模式串中出现的位置。

散列表预处理

//b模式串，m模式串的长度，bc散列表
private static final int SIZE = 256;//全局变量
private void generateBC(char[] b, int m, int[] bc) {
    for(int i = 0; i < SIZE; ++i) {
        bc[i] = -1;//初始化bc
    }
    for(int i = 0; i < m; ++i) {
        int ascii = (int)b[i];//计算b[i]的ASCII值
        bc[ascii] = i;
    }
}

坏字符

public int bm(char[] a, int n ,char[] b, int m) {
    int bc[] = new int[SIZE];//记录模式串中每个字符最后出现的位置
    generateBC(b, m, bc);//构建坏字符哈希表
    int i = 0;//i表示主串与模式串对齐的第一个字符
    while(i <= n-m) {
        int j;
        for(j = m - 1; j >= 0; --j) {//模式串从后往前匹配
            if(a[i+j] != b[j]) break;//坏字符对应模式串中的下标是j
        }
        if(j < 0) {
            return i;//匹配成功，返回主串与模式串第一个匹配的字符的位置
        }
        //相当于将模式串往后滑动j-bc[(int)a[i+j]]位
        i = i + (j - bc[(int)a[i+j]]);
    }
    return -1;
}

好后缀

• 在模式串中，查找跟好后缀匹配的另一个子串；
• 在好后缀的后缀子串中，查找最长的、能跟模式串前缀匹配的后缀子串；

好后缀也是模式串本身的后缀子串，可以在模式串和主串正式匹配之前，通过预处理模式串，预先计算好模式串的每个后缀子串，对应的另一个可匹配子串的位置。
后缀子串的最后一个字符的位置是固定的，下标为m-1，只需要纪录长度就可以了。通过长度，可以确定一个唯一的后缀子串。

引入变量suffix数组。suffix数组的下标k，表示后缀子串的长度，下标对应的数组值存储的是，在模式串中跟好后缀(u)相匹配的子串(u*)的起始下标值。
如果模式串中有多个(大于1个)子串跟后缀子串{u}匹配，为了避免模式串往后滑动得过头了，suffix数组中存储模式串中最靠后的那个子串的起始位置，也就是下标最大的那个子串的其实位置。(滑动的距离小)

引入另外一个boolean类型的prefix数组，记录模式串的后缀子串是否能匹配模式串的前缀子串。

计算并填充两个数组的值。
拿下标从0到i的子串(i可以是0到m-2)与整个模式串，求公共后缀子串，如果公共后缀子串的长度是k，那就记录suffix[k]=j(j表示公共后缀子串的起始下标)。
如果j=0，说明，公共后缀子串也是模式串的前缀子串，记录prefix[k]=true。

计算suffix与prefix

//b表示模式串，m表示模式串长度
private void generateGS(char[] b, int m, int[] suffix, boolean[] predix) {
    for(int i = 0; i < m; ++i) {//初始化
        suffix[i] = -1;
        prefix[i] = false;
    }
    for(int i = 0; i< m - 1; ++i) {
        int j = i;
        int k = 0;//公共后缀子串长度
        while(j >= 0 && b[j] == b[m-1-k]) {//与b[0,m-1]求公共后缀子串
            --j;
            ++k;
            suffix[k] = j+1;//j+1表示公共后缀子串在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位。
如果两条规则都没有找到可以匹配好后缀及其后缀子串的子串，就将整个模式串后移m位。

BM算法

//a,b表示主串和模式串；n,m表示主串和模式串的长度
public int bm(char[] a, int n, char[] b, int m) {
    int[] bc = new int[SIZE];//记录模式串中每个字符最后出现的位置
    generateBC(b,m,bc);//构建坏字符哈希表
    int[] suffix = new int[m];
    boolean[] prefix = new boolean[m];
    generateGS(b,m,suffix,prefix);
    int i = 0;//j表示主串与模式串匹配的第一个字符
    while (i <= n-m) {
        int j;
        for(j = m - 1; j >= 0; --j) {//模式串从后往前匹配
            if(a[i+j] != b[j]) break;//坏字符对应模式串中的下标是j
        }
        if(j < 0) {
            return i;//匹配成功，返回主串与模式串第一个匹配的字符的位置
        }
        int x = j - bc[(int)a[i+j]];
        int y = 0;
        if(j < m-1) {//如果有好后缀的话
            y = moveByGS(j,m,suffix,prefix);
        }
        i = i + Math.max(x,y);
    }
    return -1;
}

//j表示坏字符对应的模式串中的字符下标;m表示模式串长度
private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
    int k = m - 1 -j;//好后缀长度
    if(suffix[k] != -1) return j-suffix[k]+1;
    for(int r = j+2; r <= m-1; ++r) {
        if(prefix[m-r] == true) {
            return r;
        }
    }
    return m;
}

性能分析及优化

内存消耗

整个算法用到了额外的3个数组，其中bc数组的大小跟字符集大小有关，suffix数组和prefix数组的大小跟模式串长度m有关。

处理字符集很大的字符串匹配问题，bc数组对内存的消耗会比较多，好后缀和坏字符规则是独立的，如果对内存要求苛刻，可以只是用好后缀规则，不使用坏字符规则，可以避免bc数组过多的内存消耗。

执行效率

极端情况下，suffix数组、prefix数组的预处理的时间复杂度为O(m²)。
优化待扩展。