#include
typedef struct
{
char *ch;
int len;
}st;//字符串结构定义
void getnext(st substr,int next[])//覆盖函数
{
int i=0,j=-1;
next[0]=-1;
while (i<substr.len)
{
if(j==-1||substr.ch[i]==substr.ch[j])
{
next[++i]=++j;
}
else
j=next[j];
}
}
//以下是主要算法-kmp
int kmp(st str,st substr,int next[])
{
int i=0,j=0;
while (i<str.len && j<substr.len)
{
if(str.ch[i]==substr.ch[j])
{
++i;
++j;
}
else
{
j=next[j];
if(j==-1)
{
j=0;
++i;
}
}
}
if (j==substr.len)
return i-substr.len;
else return -1;
}
//主函数
int main()
{
int next[100];
int position;
st str;
st substr;
puts("请输入一段文章:");
gets(str.ch);
puts("请输入您想找到的一段文字:");
gets(substr.ch);
getnext(substr,next);
position = kmp(str,substr,next);
if(position!=-1)
printf("%d",position);
else
puts("error");
}
两个问题
1.在结构体中只定义了一个char指针而不是char数组,既然是指针却又没有在main函数中给其分配内存就直接使用gets函数试图写入内存,导致程序崩溃。
//解决方法一: 直接将ch定义为char数组,至于大小看情况自行修改
typedef struct
{
char ch[100];
int len;
}st;//字符串结构定义
//解决方法二: 在main函数中动态分配内存后再使用gets函数
str.len = strlen(str.ch);
substr.len = strlen(substr.ch);
你的两个子函数写的就很有问题,仔细看看吧