我的KMP算法C实现，错在哪了？
/*偶是新人，各位多多关照和体谅~认为自己解答比较精彩的告诉我怎么给分，偶新、新、新来的~*/
/* 我的那两个获得next[]和nextval[]的函数可能和严胃敏的不完全一样，
各位在不改变我的算法的前提下看看我哪儿错了~ */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int *getNext(char *P) //求模式串数组P[]的next[],注意下标从0开始!
{
int k, j;
int *next=(int *)malloc( sizeof(int)*strlen(P) );
next[0]=-1; next[1]=0;
k=0; j=1;
while(P[j]!= '\0 ') //当P[j]为字符串结束字符 '\0 '时，退出
{
if (k==-1||P[k]==P[j])
{
next[j+1] = k+1;
k = next[++j];
}
else k = next[++j];
}
return next;
}
int *getNextval(char *P,int *next) //根据next[]求nextval[]
{
int j, k;
int *nextval=(int *)malloc( sizeof(int)*strlen(P) );
for(j=0;P[j]!= '\0 ';++j) //当P[]为字符串结束字符 '\0 '时，退出
{
k=next[j];
L:if(P[j]!=P[k]) nextval[j]=k;
else {k=next[k]; goto L; }
}
return nextval;
}
int main()
{
/*
求模式串P[]在主串S[]中的第pos个字符之后（包裹pos）的位置。
其中P[]非空，1 < = pos < = strlen(S)
*/
char P[]= "aacaab ";
char S[]= "fsoifhewgsdksdkfhsdifhewhfefksdhfdsoihfoehfosdhfdsaacaab ";
int pos=3;
int i=pos,j=0;
int *next=(int *)malloc( sizeof(int)*strlen(P) );
int *nextval=(int *)malloc( sizeof(int)*strlen(P) );
next=getNext(P);
nextval=getNextval(P,next);
while(S[i]!= '\0 '&&P[j]!= '\0 ')//当P[j]或S[i]为字符串结束字符 '\0 '时退出
{
if(j==-1||S[i]==P[j]) {++i;++j;}//继续比较后续字符
else j=nextval[j]; //模式串向右移动
}
if(j> strlen(P)) //匹配成功
{
printf( "匹配成功于第%d个字符\n ",i-strlen(P));
return i-strlen(P); //返回模式串在主串中的第pos个字符之后的位置
}
else
{
printf( "匹配失败!\n ");
return 0;//匹配失败返回0
}
system( "PAUSE ");
}
[解决办法]
比较一下这个正确的getNext函数和你那个函数
void getNext(const char* pattern,int next[])
{
int k=-1,j=0;
next[0]= -1;
while(pattern[j] != '\0 ')
{
if(k!= -1 && pattern[k]!= pattern[j] )
k=next[k];
++j;++k;
if(pattern[k]== pattern[j])
next[j]=next[k];
else
next[j]=k;
}
}
