KMP算法,while循环中j<t.length()出错

Question

#include <iostream>
using namespace std;

int BF(string duan, string qiao, int pos);
void getNext(string t, int* next);
int KMP(string t, string s, int pos);
int main()
{
    string s("henuuniversitydph123qwe");
    string t("dph");
    cout << KMP(t,s,4);
    return 0;
}

int BF(string t, string s, int pos)
{
    int i = pos;      //主串开始位置
    int j = 0;       //模式串
    while (j < t.length()&& i < s.length()  )       //都没有结束
    {
        
        if (s.at(i) == t.at(j))
        {
            ++i;
            ++j;
        }
        else
        {
            i = i - j + 1;    //
            j = 0;
        }
    }
    if (j >= t.length())
    {
        for (int k = i-t.length(); k < i; k++)
        {
            cout << s.at(k);
        }
        cout << endl;
        return i - t.length();
    }
    else
    {
        return -1;
    }
}

 

int KMP(string t, string s, int pos)
{
    int i = pos;    //标志主串开始寻找的位置
    int j = 0;         //模式串位置标记
    int* next = new int[t.length()];
    getNext(t, next);
    while ((i < s.length()) && (j < t.length()))
    {
        if (j== -1 ||t.at(j) == s.at(i))
        {
            ++i;
            ++j;
        }
        else
        {
            j = next[j];
        }

    }
    if (j >= t.length())
    {
        return i - t.length();
    }
    else
        return -1;
}

void getNext(string t, int* next)
{
    int i = 0;      //模式串从0开始
    int j = -1;      //其实就是K
    next[0] = -1;
    while (i < t.length())
    {
        if (j == -1 || t[i]==t[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
}

 

 

 

 

请问，在while循环哪里出现了问题，只要我把t.length()修改成j < tlength结果就是正确的。

Answer 1

typedef struct SString {
    int leng;
    char data[MAXSTRLEN+1];   //第一个位置不使用
}SString;

void get_next(SString T, int next[]){
    int i=1,j=0;
    next[1]=0;
    while(i<T.leng)
        if(j==0 || T.data[i]==T.data[j]) {i++;j++;next[i]=j;}
        else j = next[j];
}

这是我用结构体写的。我这个是对的，你可以参考着改一改试试