字符串匹配算法之 BM 算法

BM 算法核心思想

前面说过 BF 算法和 RK 算法的思路是，在匹配完主串的字串和模式串之后，是向后移动一位，然后再从第一个字符开始匹配，而 BM 算法主要是在匹配字符的顺序和滑动的位数有所不同。

坏字符规则

BF 算法和 RK 算法在进行字符比较的时候，都是按照模式字符串的索引从小到大进行比较，而 BM 算法是从大到小进行匹配。在匹配的过程中发现某个字符不一样，主串中的这个字符称作为坏字符

然后拿着这个坏字符在模式串中查找，如果不存在这个坏字符，那直接将模式字符串移动到这个坏字符的后面

但是如果发现存在这个坏字符，就滑动模式字符串，将这两字符位置对应上，如果在模式字符串中出现多个，就选择最靠后的那个，因为这样不会让模式串滑动过多，导致错失匹配，然后再从后往前开始匹配，重复上面的规则

滑动的规律
把坏字符对应模式串的字符的下标记为 si，如果坏字符在模式字符串存在，那存在的那个位置记为 xi，如果不存在就直接记为-1，那么模式串滑动的位数就是 si-xi。

还有一种情况就是，坏字符可能在模式字符串中存在多个位置，这时就以最靠右的那个，以免滑动过多导致漏过匹配的字串。

好后缀规则

就是在从后往前匹配的时候，发现开始有几个字符是一样的，再匹配才出现坏字符，这个时候把相同的那些字符作为一个后缀处理。

和坏字符的思路差不多，把一样的字符当做一个整体后缀来看待，拿着这个好后缀在模式字符串中查找，如果找到与好后缀一样的，就把模式字符串滑动的，和后缀对应的位置上，如果不存在，就直接滑动到好后缀的后面。

但是这里和坏字符规则有点儿不同，如果直接移动到好后缀的后面，可能会出现漏调可以匹配的情况，看图说话

这种情况就是，好后缀中有部分字符和模式串中的字符是重合的，所以这里不仅要考虑好后缀是否在模式串中有匹配的情况，还要考虑好后缀的子串与模式串的匹配情况。主要是好后缀字符串的后缀字串和模式字符串的前缀字串。
后缀子串就是从后往前看，以最后一个字符开头的字串，比如 sdfg 字符串，那后缀字串就是 g，fg，dfg，前缀子串刚好和后缀字串相反，从前往后看，以第一个字符开头的子串，那前缀字串就是，s，sd，sdf。

此时好后缀如果在模式字符串中出现不匹配的时候，就不能直接滑动的好后缀的后面了，要取出好后缀的最长后缀并且能和模式字符串的前缀字串相匹配的，然后滑动到对应的位置，如果没有还是直接滑动到好后缀的后面。

那如何选择使用哪个规则呢，可以根据两个规则分别计算出滑动的位数，取最大值进行滑动。

代码实现

public class BM {
    private static final int SIZE = 256;

    private void generateBC(char[] patStr, int patLength, int[] bc) {
        // 初始化散列表
        for (int i = 0; i < SIZE; i++) {
            bc[i] = -1;
        }
        // 根据ascii值记录字符的位置
        for (int i = 0; i < patLength; i++) {
            int ascii = patStr[i];
            bc[ascii] = i;
        }
    }

    public int bm(char[] mainStr, int mainLength, char[] patStr, int patLength) {
        int[] bc = new int[SIZE];
        // 这里数组作为散列表，索引就是ascii值，存的是字符在模式字符串中的位置，根据字符计算出ascii值就可以快速获取位置
        generateBC(patStr, patLength, bc);
        int i = 0;
        while (i <= mainLength - patLength) {
            int j;
            // 遍历模式字符串，如果发现不匹配的字符，那就停止查找，这个时候j就是坏字符在模式串中的位置
            for (j = patLength - 1; j > 0; j--) {
                if (mainStr[i + j] != patStr[j]) {
                    break;
                }
            }
            // 如果j小于，就是说在模式字符串中没有坏字符，完全匹配，就找到了，直接返回i
            // 也就是模式字符串开头字符在主串中的位置
            if (j < 0) {
                return i;
            }
            // mainStr[i + j] 取出的就是坏字符，bc[mainStr[i + j]]在散列表中查找坏字符，如果有就返回就返回在模式串中的位置
            // j -  bc[mainStr[i + j]] 就是滑动的位数
            i = i + (j - bc[mainStr[i + j]]);
        }
        return -1;
    }

}

好后缀的处理方法，后面再加，，有点儿复杂。。。。头大

好后缀规则处理

好后缀规则处理最核心的内容：

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

再来回顾一下好后缀的定义，在后向前匹配的过程中，一样的几个字符构成的一个后缀，那他同时也是模式字符串的后缀。
那么如果提前计算好每种模式串后缀，对应的另一个在模式串中可匹配的子串的位置，在实际进行比较的过程，就可以直接计算出滑动位位数了。
可能不好理解，换个说法，所有可能的好后缀，一定都是模式串的后缀，好后缀的第一个处理内容是查找好后缀在模式串中匹配的另一个子串，那么就可以替换成查找模式字符串的后缀字串在模式字符串中匹配的另一个子串的过程。
第二个处理内容，同理，是查找好后缀的后缀子串，无论有多少种后缀字串，那也都可以替换成模式串的后缀子串。
那预处理都该处理什么内容呢？两个，获取所有可能的后缀字串，并计算它匹配另一个字串的位置。

字符串的所有可能的后缀字串的长度都是固定的，那么我们就可以用一个数组来存储处理内容，数组的索引作为后缀子串的长度，元素作为后缀子串匹配到的位置。

    /**
     *
     * @param patStr 模式字符串
     * @param patLength 模式字符串长度
     * @param suffix  散列表 下表作为公共后缀字串的长度，存储的是公共后缀子串的起始下标
     * @param prefix 记录模式串的后缀子串是否能匹配模式串的前缀子串，索引也是公共后缀子串的长度，这个目的是解决如果好后缀没有匹配到子串的时候，直接滑动到好后缀后面可能会出现过度滑动的情况，什么'
     *               时候就过度滑动了呢，当好后缀的最长后缀子串和模式串的前缀子串相匹配的时候，
     */
    private void generateGS(char[] patStr, int patLength, int[] suffix, boolean[] prefix) {
        for (int i = 0; i < patLength; i++) {
            suffix[i] = -1;
            prefix[i] = false;
        }
        
        // 与处理的过程，
        // 1、查找和后缀子串匹配的子串的位置，
        // 2、查找和后缀字串匹配的前缀子串
        // i 控制截取字串的长度
        for (int i = 0; i < patLength - 1; i++) {
            int j = i;
            int k = 0; // 表示公共后缀字串长度
            // 子串和模式字符串都是从后往前开始遍历，寻找公共后缀字串，当j变为-1的时候说明，
            // 后缀子串和某个子串都遍历完了，并且是匹配的，这个时候子串也是一个前缀子串
            while (j >= 0 && patStr[j] == patStr[patLength - 1 - k]) {
                k++; // 公共后缀字串的长度
                suffix[k] = j;
                j--;
            }
            // 表示某个字串既是前缀字串又是后缀子串
            // 上面的循环。如果子串
            if (j == -1) {
                prefix[k] = true;
            }
        }
    }

接下来就是计算滑动位数

private int moveByGS(int j, int patLength, int[] suffix, boolean[] prefix) {
        // j表示的是坏字符对应在模式串中的位置
        // 好后缀的长度
        int k = patLength - 1 - j;
        if (suffix[k] != -1) {
            // suffix[k]是好后缀匹配到的另一个字串对的起始位置
            /**
             *
             * m n o p b c x y z 主串
             * a b c d b c       模式串
             * p就是坏字符，他的索引是3, 好后缀是bc，另一个匹配的字串位置是1，滑动的结果是两个b刚好上下对应
             * 实际的滑动位数就是 3 - 1 + 1
             */
            return j - suffix[k] + 1;
        }
        // 如果不存在匹配的另一个子串，就要考虑好后缀的后缀子串，和前缀子串的匹配情况，来计算滑动位数
        /**
         * 这种情况就是好后缀没有可匹配的子串，需要考虑好后缀的后缀子串了
         * 
         * 坏字符的位置是3，好后缀的后缀子串的开始位置，就是5，也就是4+2
         * m n o p b c x y z 主串
         * a s c d b c       模式串
         * 
         */
        for (int r = j + 2; r <= patLength - 1; r++) {
            // patLength - r 好后缀子串的后缀子串的长度
            if (prefix[patLength - r]){
                return r;
            }
        }
        // 如果说 好后缀既没有匹配的子串，好后缀子串也没有匹配的前缀子串，
        // 那就直接滑动到好后缀的后面，滑动位数就是模式串的长度
        return patLength;
    }

完整版的 BM 算法

public int bm(char[] mainStr, int mainLength, char[] patStr, int patLength) {
        int[] bc = new int[SIZE];
        // 这里数组作为散列表，索引就是ascii值，存的是字符在模式字符串中的位置，根据字符计算出ascii值就可以快速获取位置
        generateBC(patStr, patLength, bc);
        // suffix数组用来记录模式字符串后缀子串匹配到的另一个字串的位置
        int[] suffix = new int[patLength];
        // prefix数据用来记录模式字符串后缀子串是否匹配到了前缀字串
        boolean[] prefix = new boolean[patLength];
        generateGS(patStr, patLength, suffix, prefix);
        int i = 0;
        while (i <= mainLength - patLength) {
            int j; // j表示主串与模式串匹配的第一个字符
            // 遍历模式字符串，如果发现不匹配的字符，那就停止查找，这个时候j就是坏字符在模式串中的位置
            for (j = patLength - 1; j > 0; j--) {
                if (mainStr[i + j] != patStr[j]) {
                    break;
                }
            }
            // 如果j小于，就是说在模式字符串中没有坏字符，完全匹配，就找到了，直接返回i
            // 也就是模式字符串开头字符在主串中的位置
            if (j < 0) {
                return i;
            }
            // mainStr[i + j] 取出的就是坏字符，bc[mainStr[i + j]]在散列表中查找坏字符，如果有就返回就返回在模式串中的位置
            // j -  bc[mainStr[i + j]] 就是滑动的位数
            int x = j - bc[mainStr[i + j]]; // 坏字符规则计算出的移动位数
            int y = 0;
            // j < patLength - 1 表示是有好后缀存在的，所以需要计算一下好后缀规则下，滑动的位数
            if (j < patLength - 1) {
                y = moveByGS(j, patLength, suffix, prefix);
            }

            i = i + Math.max(x, y);
        }
        return -1;
    }