BM算法

BM算法(Boyer-Moore)不仅效率高，而且构思巧妙，是十分有效的字符串匹配算法，比KMP算法要更加高效。

对于上图的示例，BM算法采用了尾部比较的方法，具体来说就是：字符串与搜索词头部对齐，从尾部开始搜索，然后直接从尾部比较。
其定义了坏字符规则和好后缀规则。
坏字符规则：

如上图两者首次匹配时，尾部S与E不匹配，则称S为坏字符，此时在搜索词中无法搜索到坏字符S，因此直接将搜索词移动到S后。

若坏字符P在搜索词中能够找到，则将字符串与搜索词中的P对齐。
因此坏字符规则可总结为：

1. 若搜索词中存在坏字符，则两者对齐
2. 若搜索词中不存在坏字符，则直接移动到坏字符后
   用公式表示为：

后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置

若坏字符不存在与搜索词中，则上次出现位置为-1
其实就是：后移位数 = 搜索词长度 - 搜索词中上次出现的位置。上次出现的位置是从右往左寻找的。如坏字符B与搜索词ABABA，则上次出现的位置为从右往左的第二位B。
好后缀规则:

若字符串MPLE与搜索词匹配，则MPLE成为好后缀

而I与A不匹配，则I为坏字符，按照坏字符规则将移动 2-（-1）= 3位，但若按照好后缀规则：

后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置

则移动位数为6 - 0 = 6位

所谓好后缀规则就是：

1. 若好后缀在搜索词中出现，则将两者对齐，若好后缀出现多次，则与最右侧的那个对齐
2. 若好后缀只出现一次，则寻找其最大子串作为好后缀。

接着取好后缀与坏字符中移动步数较大者作为最后移动步数。

下面贴上仅实现了坏字符的代码

//BM算法：字符串搜索

#include "stdafx.h"
#include<iostream>
#include<string>
#include<vector>

using namespace std;

vector<int> preBmBc(string ps);
int main()
{
    string ts = "HERE IS A SIMPLE EXAMPLE";
    string ps = "EXAMPLE";
    vector<int> matched;
    vector<int> BC = preBmBc(ps);//创建bad character数组
    //原始字符串与模式串长度
    int tlen = ts.size();
    int plen = ps.size();
    
    int tindex = 0;//ts索引
    while (tindex+plen <= tlen) {
        int badmove = 0;
        int goodmove = 0;
        for (size_t j = plen; j > 0; j--)
        {
            if (ts[tindex + j - 1] != ps[j - 1]) {
                badmove = BC[ts[tindex+j-1]]; //bad character移动步数
                cout <<"Move step:"<< badmove << endl;
                break;
            }
            if (j == 1) {//匹配到
                matched.push_back(tindex);
                tindex += plen - 1;
                continue;
            }
        }
        tindex += badmove;

    }

    for (size_t i = 0; i < matched.size(); i++)
    {
        cout << "matched at:" << matched[i] << endl;
    }
    system("pause");
    return 0;
}


//bad character数组，256
vector<int> preBmBc(string ps) {
    vector<int> BC(256, ps.size());
    for (size_t i = 0; i < ps.size(); i++)
    {
        BC[ps[i]] = ps.size() - i - 1;
    }
    return BC;
}