Question

C语言KMP算法中的getnext函数,求详细解析！

C语言数据结构中串的模式匹配,其算法是 KMP算法，其中的getnext函数我看不是很懂阿，求解析，详细解析，麻烦懂的人可以在我的代码后面添加备注，帮助我理解，小弟在此感谢了。。。
代码如下:
void getnext(string t,int *next)
{
int j,k;
j=0;k=-1;next[0]=-1;
while(j<t.len-1)
{
if(k==-1||t.ch[j]==t.ch[k])
{
j++;
k++;
next[j]=k;
}
else
k=next[k];
}
}

Answer 1

刚调试完，看不懂再问吧，你贴的那个getnext不太直观，还是按书上的理解吧
#include<iostream>

using namespace std;

#define MAXSTRLEN 255

typedef unsigned char SString[MAXSTRLEN];

int Index_KMP(SString S,SString T,int *next);
void Get_next(SString T,int *next);
void Input(SString *S);
void Display_next(SString T,int *next);
int main()
{
int next[10];
int pos;
int i=1,len=1;
SString S;
SString T;
// char P[200]="abc";
// char *q=P;
cout<<"Input moshi String:";
Input(&T);
cout<<"Input String:";
Input(&S);

// cout<<(int *)T<<" "<<&T<<endl;
// cout<<(int)T[0];
// while((T[i++]=getchar())!='\n');

// for(;T[len]!='\0';len++);
// cout<<len;
Get_next(T,next);
// Display_next(T,next);
pos=Index_KMP(S,T,next);
cout<<pos<<endl;
return 0;
}

void Display_next(SString T,int *next)
{
for(int i=1; i<(int)T[0];i++)
cout<<next[i];
}

void Input(SString *S)
{
int i=1;

while(((*S)[i++]=getchar())!='\n');
(*S)[i]='\0';
(*S)[0]=i-2;
// cout<<i;
}
void Get_next(SString T,int *next)
{
int i=1,j=0;
next[1]=0;
// cout<<(int)T[0];
while(i<(int)T[0])
{
//cout<<T[i]<<" "<<T[j]<<endl;
if(j==0||T[i]==T[j])
{
//cout<<next[i]<<endl;
i++,j++;
next[i]=j;

}
else
j=next[j];
}
}

int Index_KMP(SString S,SString T,int *next)
{
int i=1,j=1;
while(i<=(int)S[0]&&j<=(int)T[0])
{
if(j==0||S[i]==T[j])
{
i++,j++;
}
else
j=next[j];
}
if(j>(int)T[0])
return i-(int)T[0];
else
return 0;
}