字符串匹配之BM算法（Boyer-Moore）

之前写过两篇关于kmp的文章，今天发现这货，据说当pattern串长度较大的时候，表现比kmp高3-4被，果断学起来啊~
首先，BM算法中的两个比较重要的概念就是坏字符和好后缀
1. 关于坏字符
BM匹配算法跟常识性的匹配算法不同的地方，首先就在于BM匹配算法，是从模式串的最后一位开始，向前开始匹配的。
当发现第一个不匹配的位置的时候，就会出现所谓的坏字符，比如
src：a b c d e f g
pat：h  i j k
其中坏字符就是'd'，当找到坏字符的时候，我们要记录pattern串当前的下标p_i以及pattern串最大的坏字符的下标（没有按照-1处理）s_i，这样将pattern串向右滑动(p_i-s_i)个字符继续匹配即可。比如：
src: a b c d e f g
pat: b c d
第一个坏字符是'c'，p_i 是2，坏字符'c'对应的s_i是1，所以pattern串向右滑动一个字符继续匹配即可

但是，如果只是有坏字符的话，是有可能使pattern串向左滑动的，比如：
src: a a a a a a a a a
pat: b a a a 
这时就需要第二个关键先生——好后缀登场了
2. 好后缀
首先，好后缀是指在匹配的过程中已经匹配的字符串叫做好后缀，如果好后缀在模式串前半部分有匹配的，那么就直接挪到两两匹配，规则可以参照坏字符；如果没有，就需要计算好后缀的后缀集合与模式串的前缀集合相同的最大交集，以此来决定后移多少，比如：
src: a c a b c b c b a c 
pat: a b b c a b c
这里pattern串直接后移到 第一个bc匹配即可
src: a c a b c b c b a c 
pat:         a b b c a b c
至于代码，坏字符本身不难，只需要记录pattern串每个字符出现的最大下标位置即可，这里说一下好后缀：
首先，好后缀的求解分为两个部分：
a). 好后缀good_suffix在pattern串中存在相同且在其前面的good_suffix，这里只需要记录每个后缀的前向最早出现即可；
这里需要引入一个suffix数组，suffix[i]表示长度为i的模式串后缀在其之前出现的下标，没有则置-1
b)好后缀good_suffix在pattern串中不存在相同且在其前面的good_suffix，就需要求好后缀的后缀和pattern串的前缀的最大匹配
这里需要引入另一个prefix数组，prefix[i]表示长度为i的模式串后缀，是否能够匹配模式串相应的前缀，这里贴上一波这两个数组的求法

void generate_good_suffix(string &pattern, int len, vector<int> &suffix, vector<bool> &prefix){
    for(int i =0; i < len; i++){
        suffix[i]=-1;
        prefix[i]=false;
    }
    for(int i = 0; i<len-1;i++){
        int j = i;
        int k = 0;
        while(j>=0 && pattern[j]==pattern[len-1-k]){
            j--;
            k++;
            suffix[k]=j+1;
        }
        if(j==-1)prefix[k]=true;
    }
}