字符串匹配算法

　　字符串匹配也是一个比较常见的功能了，本质上，就是从一个字符串中查找另一个字符串，传说中的KMP 算法就是讲这个的，在深入了解复杂的匹配算法之前，先来看两个简单的字符串匹配算法。

　　1、暴力匹配算法（brute force）

　　假设在主串A中查找模式串B，字符串A的长度为n，模式串的长度为m，那么必然n>m，BF算法就是在主串中依次检查从位置0、1、2…n-m开始，且长度为m的这 n - m + 1个子串，依次对比这些子串和模式串，看是否匹配。可以看出来，这种算法极端情况下的时间复杂度是O(n * m)，直到最后一个子串，才发现不匹配，也就是没有查找到。

　　看起来BF算法性能比较差，但是实际工程中用的还是比较多的，因为它实现简单，而且上面那只是理论上的情况，实际中，对比长度为m的两个串时，可能中途发现不相等就直接返回了，并不需要把m个字符都遍历一遍，而且工程中主串和模式串可能都不会太长，用BF算法就足够了。

　　2、Rabin-Karp算法（简称RK算法）

　　RK算法实际上是BF算法的一个升级，它也是一个个子串去对比匹配，但是在对比两个长度为m的子串和模式串的时候，BF算法本质上是一个个比较字符，这里涉及到一次遍历，m次对比。而RK算法用的是hash，也就是先计算出了模式串的hash值，以及n - m + 1个子串的hash值，直接对比hash值是否相等，省去遍历一个个字符的操作了。如果hash值不等，那么肯定不匹配，如果hash值相等，那么大概率两个串是匹配的（因为可能有哈希碰撞），这时再来对比每一个字符即可。这就是RK算法的思想。

　　通过哈希算法计算子串的哈希值的时候，我们需要遍历子串中的每个字符。尽管模式串与子串比较的效率提高了，但是，算法整体的效率并没有提高。这里就需要设计一个高效易用的哈希算法了。比如串中只包含 a-z之间的字符，那么可以将其映射为1-26之间的数字，将一个字符串利用二进制的思想计算得到其十进制表示的数字，代表其hash值。

　　如果主串特别长，那么我们可能需要比较大的额外存储来存放子串的hash值，尤其上面的设计针对每一个子串都有不同的hash值，这里也可以稍微转变思路，即允许一定的hash冲突来解决。

　　3、Boyer-Moore算法（简称BM算法）

　　BM算法，是传说中的KMP算法性能的三四倍，但是会比较复杂。前面我们用暴力匹配方式时，每一次子串和模式串不匹配的时候，我们就往后移动一位，找下一个子串，但是实际上，是可以移动多个位置的，因为如果主串中某个字符不在模式串中的时候，那么可以直接往后跳到这个字符后面那个位置。这样一次比较失败，跳过一些肯定不会匹配的情况，减少了比较的数目，这就是BM算法的核心思想。

　　BM算法主要包括两个规则，分别是坏字符规则（bad character rule）和好后缀规则（good suffix rule），下面分别看一下。

　　（1）、坏字符规则：前面我们的算法在对比模式串和主串的子串时，都是按照模式串的下标从小到大的顺序，依次与主串中的字符进行对比的， BM算法比较特殊，它在对比时是从按照下标从大到小来匹配的，即从后往前。我们从模式串的末尾往前倒着匹配，当我们发现某个字符没法匹配的时候。我们把这个没有匹配的字符叫作坏字符（主串中的字符）。

　　前面我们找到了坏字符，然后在模式串中去查找坏字符，如果模式串不存在，那么就可以直接把模式串往后移动k个位置（后面会讲这个k是怎么计算的），直接移动到这个坏字符的后面一位。继续从模式串的最后面一位开始匹配（从后往前）。

　　但是如果坏字符在模式串中存在，那么是不能直接移动到坏字符的后面一位的，这里的核心就是到底移动多少个位置。

　　当发生不匹配的时候，我们把坏字符对应的模式串中的字符下标记作si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作xi。如果不存在，我们把xi记作-1。那模式串往后移动的位数就等于si-xi。（这里说的下标，都是字符在模式串的下标）。 attention：坏字符在模式串里多处出现，那我们在计算xi的时候，选择最靠后的那个，即最大的那个，防止一次移动的过多而疏漏。

　　利用坏字符规则，BM算法在最好情况下的时间复杂度非常低，是O(n/m)。比如，主串是aaabaaabaaabaaab，模式串是aaaa。每次比对，模式串都可以直接后移四位，所以，匹配具有类似特点的模式串和主串的时候，BM算法非常高效。　　　　不过，单纯使用坏字符规则还是不够的。因为根据si-xi计算出来的移动位数，有可能是负数，比如主串是aaaaaaaaaaaaaaaa，模式串是baaa 。计算的si = 0, xi = 3, 不但不会向后滑动模式串，还有可能倒退。所以，BM算法还需要用到“好后缀规则”。

　　（2）、好后缀规则：好后缀规则和坏字符规则的思路是很相似的，这个需要对比着王争画的图来看，比较直观，总的来说，就是从后往前比较模式串和子串时，当遇到不匹配的时候，把已经匹配成功的字符（可能是多个）叫做好后缀。记作{u}。我们拿它在模式串中查找，如果找到了另一个跟{u}相匹配的子串{u*}，那我们就将模式串滑动到子串{u*}与主串中{u}对齐的位置。

　　如果在模式串中找不到另一个等于{u}的子串，我们就直接将模式串，滑动到主串中{u}的后面，因为之前的任何一次往后滑动，都没有匹配主串中{u}的情况。这里有一个问题？过度滑动，具体可以参考图中的举例。这里本质原因是因为，好后缀和模式串的前缀有重叠，如果直接滑动到主串中{u}的后面，就会有漏过的风险。

　　所以，针对这种情况，我们不仅要看好后缀在模式串中，是否有另一个匹配的子串，我们还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。所谓某个字符串s的后缀子串，就是最后一个字符跟s对齐的子串，比如abc的后缀子串就包括c, bc。所谓前缀子串，就是起始字符跟 s对齐的子串，比如abc的前缀子串有a，ab。这里滑动的位数就会有变化。

　　当模式串和主串中的某个字符不匹配的时候，如何选择用好后缀规则还是坏字符规则，来计算模式串往后滑动的位数？我们可以分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的，作为模式串往后滑动的位数。这种处理方法还可以避免我们前面提到的，根据坏字符规则，计算得到的往后滑动的位数，有可能是负数的情况。

　　BM算法代码实现

　　在坏字符规则中，难点在于计算xi的值，即坏字符在模式串中的位置（多个则取最后一个），如果拿坏字符去模式串中顺序遍历，就比较低效了，这里可以利用查表法，将模式串中的每个字符及其下标都存储在散列表中，这样就能快速查找了。我们先来看一下坏字符规则下的BM算法实现，暂时不考虑一些负面情况。

    private final int SIZE = 256;

    //构造散列表，存储模式串中每一个字符的下标，这里如果有重复字符，那么bc中记录的是最后一个字符的下标，即坏字符散列表
    private void generateBC(char[] b, int m, int[] bc) {
        for (int i = 0; i < SIZE; i++) {
            bc[i] = -1;
        }
        for (int i = 0; i < m; i++) {
            int ascii = b[i];
            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;  //表示主串与模式串对齐的第一个字符，它控制向后滑动，即从主串中第几个字符开始比较
        while (i <= n - m) {
            int j;
            for (j = m - 1; j >= 0; j--) {  //模式串从后往前匹配
                if (a[j + i] != b[j]) break; //此时坏字符对应的模式串中的字符的下标是j，坏字符本身就是a[i+j]
            }
            if (j < 0) {
                return i;  //匹配成功，返回主串与模式串第一个匹配的字符的位置
            }

            i += (j - bc[a[i + j]]);  //模式串向后滑动j - bc[a[i+j]]位，即位数。
        }
        return -1;
    }

　　上面就是坏字符规则的代码，好后缀规则要更加复杂一点，先再次看一下好后缀规则的核心内容：

1）在模式串中，查找跟好后缀匹配的另一个子串（这里如果有多个，是找第一个还是最后一个呢，总之就是移动的位数更小的那个）；
2）在好后缀的子串中，查找最长的，能够跟模式串前缀子串相匹配的后缀子串。

　　显然，这两个操作不能使用暴力方法求解，那样BM算法就不高效了。因为好后缀也是模式串本身的后缀子串，所以，我们可以在模式串和主串正式匹配之前，通过预处理模式串，预先计算好模式串的每个后缀子串，对应的另一个可匹配子串的位置。这里本质上还是使用空间换时间的思路，提前用一个哈希表来把待查询的数据缓存起来。

　　如何表示模式串中不同的后缀子串呢？因为后缀子串的最后一个字符的位置是固定的，下标为m-1，我们只需要记录长度就可以了。通过长度，我们可以确定一个唯一的后缀子串。

　　这里要引入最关键的变量suffix数组。suffix数组的下标k，表示后缀子串的长度，下标对应的数组值存储的是，在模式串中跟后缀{u}相匹配的子串{u*}的起始下标值。如果模式串中有多个（大于1个）子串跟后缀子串{u}匹配，那suffix数组中该存储哪一个子串的起始位置呢？为了避免模式串往后滑动得过头了，我们肯定要存储模式串中最靠后的那个子串的起始位置，也就是下标最大的那个子串的起始位置。也就是说，我们要提前计算好这个suffix数组，这样我们就能够实现目标1）了，在模式串中能够查到跟好后缀匹配的另一个子串的位置。

　　但是对于目标2），在好后缀的子串中，查找最长的，能够和模式串前缀子串相匹配的后缀子串。因此这里我们还需要另一个数组prefix，表示模式串的后缀子串是否能够和其前缀子串相匹配，这个数组的下标可以和上面suffix数组的下标一致，都是后缀子串的长度，值是boolean类型，表示这个后缀子串是否有相匹配的前缀子串。

　　难点：如何计算这两个数组的值

　　整个计算过程比较巧妙，需要好好理解一下，我们拿下标从0到i的子串（i可以是0到m-2）与整个模式串，求公共后缀子串。如果公共后缀子串的长度是k，那我们就记录suffix[k]=j（j表示公共后缀子串的起始下标）。如果j等于0，也就是说，公共后缀子串也是模式串的前缀子串，我们就记录prefix[k]=true。代码如下：

    private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
        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），那么就可以将模式串向后移动 j - suffix[k] + 1个位（j表示坏字符对应的字符在模式串中的下标）；如果suffix[k] = -1，那么意味着模式串中不存在另一个跟好后缀相匹配的字符串，这样就要。

　　先暂停一下字符串匹配算法，这个可以梳理的太多了。