Boyer Moore 简易算法

Boyer Moore是从子串的右到左搜索的，当然搜索主串文本的顺序还是从左到右的。虽然是简化版，但是速度也不比KMP差。

如下图：

如图比较到N的时候与E不匹配，那么我们就在子串里面NEEDLE看看有没有N这个字母，刚好是有的，所有就移到子串N的位置进行比较，那么一下子就跃进了很多了； 在看到了S的位置，不匹配，看看子串里面有没有S这个字母，没有，所以我们整个子串都右移，如此反复最后就找到匹配的了。只比较了4次失败的，加上最后一次成功的6个字母比较，才比较了10次。速度很快。

下面看看它和暴力法的对比程序：

#include  
#include  
#include  
#include  
  
using namespace std;  
  
class BoyerMoore  
{  
public:  
    BoyerMoore(string pat);  
  
    int search(string text);  
  
private:  
    vector rightSkip;  
    string pat;  
};  
  
BoyerMoore::BoyerMoore(string pa):pat(pa)  
{  
    rightSkip.resize(256, -1);  
    int j = 0;  
    for (auto s:pat)  
        rightSkip[s] = j++;  
}  
  
int BoyerMoore::search(string text)  
{  
    int n = text.length();  
    int m = pat.length();  
    int skip = 0;  
    for (int i = 0; i < n-m; i+=skip)  
    {  
        skip = 0;  
        for (int j = m-1; j >





= 0; j--)  
        {  
            if (pat[j] != text[i+j])  
            {  
                skip = j - rightSkip[text[i+j]];  
                if(skip < 1) skip = 1;  
                break;  
            }  
        }  
        if(skip == 0) return i;  
    }  
    return n;  
}  
  
vector bfSearch(string &text, string &substr)  
{  
    vector begIndex;  
    int n = text.size();  
    int m = substr.size();  
  
    //注意这里是i<=n-m不是i vibf = bfSearch(str1,substr1);  
  
    for (int i = 0; i < vibf.size(); i++)  
    {  
        cout< 
 

记录了出现子串的下标，初次出现的结果是一样的。暴力法记录了全部出现的初次下标。