数据结构—KMP模板

╰+攻爆jí腚メ 2022-07-30 13:13 137阅读 0赞

/*
    编写一个程序，实现顺序串的各种模式匹配运算，并完成下面功能：
    （1）建立目标串s "abcabcdabcdeabcdefabcdefg"和模式串t "abcdeabcdefab";
    （2）采用简单匹配算法求t在s中的位置；
    （3）对模式串t求next数组值和nextval数组值；
    （4）采用KMP算法求t在s中的位置。
    */
    #include <iostream>
    #include <string.h>
    #define MaxSize 100
    using namespace std;
    typedef struct
    {
        char data[MaxSize];
        int length;
    } SqString;
    void StrAssign(SqString &s,char cstr[])   //将一个字符串常量赋给串s，即生成一个其值等于cstr的串s
    {
        int i;
        for(i=0; cstr[i]!='\0'; i++)
            s.data[i]=cstr[i];
        s.length=i;
    }
    void DispStr(SqString s)              //输出串的所有元素值
    {
        int i;
        if(s.length>0)
        {
            for(i=0; i<s.length; i++)
                cout<<s.data[i];
            cout<<endl;
        }
    }
    void GetNext(SqString t,int next[])
    {
        int j,k;
        j=0,k=-1,next[0]=-1;
        while(j<t.length-1)
        {
            if(k==-1||t.data[j]==t.data[k])
            {
                j++;
                k++;
                next[j]=k;
            }
            else
                k=next[k];
        }
    }
    void GetNextval(SqString t,int nextval[])
    {
        int j,k;
        j=0,k=-1,nextval[0]=-1;
        while(j<t.length)
        {
            if(k==-1||t.data[j]==t.data[k])
            {
                j++;
                k++;
                if(t.data[j]!=t.data[k])
                    nextval[j]=k;
                else
                    nextval[j]=nextval[k];
            }
            else
                k=nextval[k];
        }
    }
    int KMPIndex(SqString s,SqString t)
    {
        int next[MaxSize],i=0,j=0;
        GetNext(t,next);
        while(i<s.length&&j<t.length)
        {
            if(j==-1||s.data[i]==t.data[j])
            {
                i++;
                j++;
            }
            else
                j=next[j];
        }
        if(j>=t.length)
            return (i-t.length);
        else
            return (-1);
    }
    int KMPIndex1(SqString s,SqString t)
    {
        int nextval[MaxSize],i=0,j=0;
        GetNextval(t,nextval);
        while(i<s.length&&j<t.length)
        {
            if(j==-1||s.data[i]==t.data[j])
            {
                i++;
                j++;
            }
            else
                j=nextval[j];
        }
        if(j>=t.length)
            return (i-t.length);
        else
            return (-1);
    }
    int main()
    {
        SqString s,t;
        int next[MaxSize],nextval[MaxSize];
        StrAssign(s,"abcabcdabcdeabcdefabcdefg");
        StrAssign(t,"abcdeabcdefab");
        cout<<"串s:";
        DispStr(s);
        cout<<"串t:";
        DispStr(t);
        cout<<endl;
        GetNext(t,next);
        cout<<"next数组值为:";
        for(int i=0;i<t.length;i++)
        {
            cout<<next[i]<<" ";
        }
        cout<<endl;
        GetNextval(t,nextval);
        cout<<"nextval数组值为:";
        for(int i=0;i<t.length;i++)
        {
            cout<<nextval[i]<<" ";
        }
        cout<<endl;
        cout<<"采用KMP算法求t在s中的位置："<<KMPIndex(s,t)<<endl;
        cout<<"采用修正后的KMP算法求t在s中的位置："<<KMPIndex1(s,t)<<endl;
        return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220724/aaa77c80502c4276a9516ebdbbef01dd.png