首页 / 算法 / 字符串匹配sunday算法c++实现（转）

字符串匹配sunday算法c++实现（转）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了字符串匹配sunday算法c++实现（转），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1996字，纯文字阅读大概需要3分钟。

内容图文

转载于http://blog.csdn.net/eqmcc/article/details/8205249

sunday.h

#include <cstdlib>
#include <string>
#include <iostream>
#include <map>

#ifndef _SUNDAYDLL_H_
#define _SUNDAYDLL_H_

usingnamespace 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 mapstring pattern,text;
    int pattern_length;
    int match_offset;
};

#endif /* _SUNDAYDLL_H_ */

sunday.c

#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);
    return0;
}

 

原文：http://www.cnblogs.com/cmjason/p/3910550.html

内容总结

以上是互联网集市为您收集整理的字符串匹配sunday算法c++实现（转）全部内容，希望文章能够帮你解决字符串匹配sunday算法c++实现（转）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1106485.html

来源：【匿名】