暴力匹配算法&KMP算法

暴力匹配算法部分:

void Match(string target,string find){
    unsigned long length_t,length_f;
    int judge,judge_f;
    length_t=target.size();
    length_f=find.size();
    for(int i=0;i<length_t;i++)
    {
        judge=i;
        judge_f=0;
        for(int j=0;j<length_f;j++)
        {
//            cout<<"t:"<<target[i]<<":::f:"<<find[j]<<endl;
            if(find[j]!=target[i+judge_f])
                break;
            if(j==length_f-1)
                cout<<judge<<' ';
            judge_f++;
        }
//        cout<<endl;
    }
}

 

暴力匹配算法调用验证部分:

//暴力匹配算法验证部分
    string target,find;
    cout<<"please input target string:";
    cin>>target;
    cout<<"please input string to find:";
    cin>>find;
    Match(target, find);

 

KMP算法函数部分:

int * getNext(string p){
    int * next=new int[p.size()];
    next[0] = -1;
    int i = 0, j = -1;

    while (i < p.size())
    {
        if (j == -1 || p[i] == p[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];
    }
    return next;
}

void KMP_c(string t, string p)
{
    int i = 0;
    int j = 0;
    int * next=getNext(p);
    while (i < t.size())
    {
        if (j == -1 || t[i] == p[j])
        {
            i++;
            j++;
        }
        else
            j = next[j];
        if (j == p.size()){
            cout<<i - j<<' ';
            j=next[j];
        }
    }
}

 

KMP算法调用部分:

string S;
string T;
cin >> S;
cin >> T;
KMP_c(S, T);

 

点赞

发表评论