已知模式串t=“abcaabbabcab”，写出用KMP法求得的每个字符串对应的next和nextval函数值

#include <iostream>using namespace std;#define MAXLEN 255typedef struct{char ch[MAXLEN+1];int length;}SString;//nextvoid get_next(SString T,int next[]);//nextvalvoid get_next...

abtgu

21588人浏览 · 2020-04-18 11:25:34

abtgu · 2020-04-18 11:25:34 发布

#include <iostream>
using namespace std;
#define MAXLEN 255
typedef struct
{
    char ch[MAXLEN+1];
    int length;
}SString;

//next
void get_next(SString T,int next[]);
//nextval
void get_nextval(SString T,int nextval[]);


int main()
{
    SString T;
    cout << "Please input T:";
    for(int i=1; i<13;i++)
        cin >> T.ch[i];
    T.length = 13;
    int next[13];
    int nextval[13];
    get_next(T,next);
    get_nextval(T,nextval);
    cout << "next:" ;
    for(int i=1;i<13;i++)
        cout << next[i] << " ";
    cout << endl;
    cout << "nextval:";
    for(int i=1;i<13;i++)
        cout << nextval[i] << " ";

    return 0;
}
void get_next(SString T,int next[])
{
    int i=1,j=0;
    next[1] = 0;
    while(i<T.length)
    {
        if(j==0 || T.ch[j]==T.ch[i])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];
    }
}
void get_nextval(SString T,int nextval[])
{
    int i=1,j=0;
    nextval[1] = 0;
    while(i<T.length)
    {
        if(j==0 || T.ch[j]==T.ch[i])
        {
            ++i;
            ++j;
            if(T.ch[i] != T.ch[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        }
        else
            j = nextval[j];
    }
}