|
? ? ?下面是一位同学的KMP算法程序，调试时运行时出现了一些问题。没有错误但输出不对，找不出原因。
? ? 该同学很用功的，程序写得不错。先赞一下交表杨！
? ? 大家看看算法，并回顾思考一下改的原因。
?同学程序链接：http://blog.csdn.net/zwycaogen/article/details/40948267
#include <iostream> ?
using namespace std; ?
void GetNext(int longth,char T[],int (&next)[5]) ? ? //1.或者将此行的后半部分(&next)改成 int *next，那么后面的static就不变了。
{ ??int k=-1,j=0; ?
? ? next[0]=-1; ?
? ? while(j<longth) ?
? ? { ??if(k==-1 || T[k]==T[j]) ?
? ? ? ? { ??++k; ?
? ? ? ? ? ? ++j; ?
? ? ? ? ? ? next[j]=k; ?
? ? ? ? } ?
? ? ? ? else ?
? ? ? ? ? ? k=next[k]; ?
? ? } ?
} ?
int KMP(char S[],int next[5]) ?
{ ?? int i=0,j=0; ?
? ? while((S[i]!=' ')&&(T[j]!=' ')) ?
? ? { ??if(S[i]==T[j]) ?
? ? ? ? { ??++i; ?
? ? ? ? ? ? ++j; ?
? ? ? ? } ?
? ? ? ? else ?
? ? ? ? {?? j=next[j]; ?
? ? ? ? ? ? if(j==-1) ?
? ? ? ? ? ? {?? ++i; ?
? ? ? ? ? ? ? ? ++j; ?
? ? ? ? ? ? } ?
? ? ? ? } ?
? ? } ?
? ? if(T[j]==' ') { ?
? ? ? // ?cout<<"i="<<i<<endl; ?//这个语句没意义，是作者调试时加上的，在些删除了。
? ? ? ? return (i-j+1); ?
? ? } ?
? ? else return 0; ?
} ?
int main() ?
{ ?? char S[10]="abcabcacb"; ?
? ? char T[6]="abcac"; ?
? ? cout<<T[0]<<endl; ?
? ? static int next[5]; ?//2.或不改上面1，程序只改这个地方面。加了红色内容。
? ? GetNext(5,T,next); ? ? ? ? ? ?
? ? cout<<"T[0]="<<T[0]<<endl; ? ? ? ? //这里输出的是空格，为什么呢？应该输出是a?原来的错误地方面 ? ? for(int i=0;i<5;i++) ? ? ? ? ? cout<<"next["<<i<<"] = "<<next[i]<<endl; ? ? ?//这里i=0,j=0 跳过了上面while((S[i]!=' ')&&(T[j]!=' '))循环 ? ? ? cout<<KMP(S,next)<<endl; ? ? ? return 0; ? } ?
（编辑：洛阳站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
