#include <cstdlib>#include <string>#include <iostream>#include <map>#ifndef _SUNDAYDLL_H_#define _SUNDAYDLL_H_using namespace std;class Sunday{    public:    Sunday(string & _pattern){        pattern=_pattern;        pattern_length = pattern.size();        match_offset=-1;    }    ~Sunday(){}    // build the Bad char table using a map，计算模式串要移动的距离    void build_BC(){        for(int i=0;i<pattern_length;++i){                BC[pattern[i]]=pattern_length-i-1;//用了map            }    }    void show_BC(){        map<char,int>::iterator it= BC.begin();        while(it != BC.end()){            cout<<"["<<it->first<<"]=>"<<it->second<<"\t"<<endl;            ++it;        }    }    int calc_jump(int i){        map<char,int>::iterator it= BC.find(text[i]);        return (it==BC.end())?pattern_length:it->second;    }    void match(string & _text){        text=_text;        int text_length=text.size();        int i=pattern_length-1;        int pos=pattern_length-1;        match_offset=pattern_length-1;        while(pos<=text_length){            while(i>=0 && pattern[i]==text[pos]){--i;--pos;}            if(i<0){cout<<"match at offset: "<<match_offset-pattern_length+1<<endl;return;}            else{                pos=match_offset+1;                int jump=calc_jump(pos);                pos=pos+jump;                if(pos>text_length){cout<<"no match"<<endl;}                i=pattern_length-1;                match_offset=pos;            }        }    }    private:    map<char,int> BC; // Bad Char map    string pattern,text;    int pattern_length;    int match_offset;};#endif /* _SUNDAYDLL_H_ */

#include <cstdlib>#include <string>#include <iostream>#include "sunday.h"int main(){    string pattern = "search";    string text = "substring searching algorithm";    cout<<"pattern: "<<pattern<<endl;    cout<<"text: "<<text<<endl;    Sunday * sunday = new Sunday(pattern);    sunday->build_BC();    //sunday->show_BC();    sunday->match(text);    return 0;}