关于KMP算法
设定初始字符串“whara thara's a will, thara's a way.”,输入字符串“ere”,利用KMP算法将“ara”替换成“ere”。其他代码写好了但是主函数一直出问题,求指点。
#include<stdio.h>
#define MaxSize 100
typedef struct
{
char data[MaxSize];
int length;
}SqString;
SqString RepStr(SqString s,int i,int j,SqString t)
{
int k;
SqString str;
str.length=0;
if(i<=0||i>s.length||i+j-1>s.length)
return str;
for(k=0;k<i-1;k++)
str.data[k]=s.data[k];
for(k=0;k<t.length;k++)
str.data[i+k-1]=t.data[k];
for(k=i+j-1;k<t.length;k++)
str.data[t.length+k-j]=s.data[k];
str.length=s.length-j+t.length;
return str;
}
void GetNextval(SqString t,int nextval[])
{ int j=0,k=-1;
nextval[0]=-1;
while(j<t.length)
{ if(k==-1||t.data[j]==t.data[k])
{ j++;k++;
if(t.data[j]!=t.data[k])
nextval[j]=k;
else
nextval[j]=nextval[k];
}
else
k=nextval[k];
}
}
int KMPIndex(SqString s,SqString t)
{
int nextval[MaxSize],i=0,j=0;
GetNextval(t,nextval);
while(i<s.length&&j<t.length)
{ if(j==-1||s.data[i]==t.data[j])
{
i++;
j++;
}
else j=nextval[j];
}
if(j>=t.length)
return (i-t.length);
else
return(-1);
}
void DispStr(SqString s)
{
int i;
if(s.length>0)
{
for(i=0;i<s.length;i++)
printf("%c",s.data[i]);
printf("\n");
}
}