关于KMP算法的一个问题

hhhh还好还好 · 发表于 2018-10-17 18:03:24

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

//准确来说这个问题不是关于KMP算法的，具体问题在代码中的注释

#include <stdio.h>
#include <stdlib.h>
#define max_size 100

typedef struct
{
char a[max_size];
int length;
}string,*STRING;

void initstring(STRING L)       //初始化L
{
int i;
printf("Çëêäèë×Ö·ûêyÄ¿:");
scanf("%d",&L->length);       //这个是输入长度

printf("Çëêäèë′yÆ￥Åä′®»òÕßÄ￡ê½′®:");
for(i=1;i<=L->length;i++)
scanf("%c",&L->a[i]);    //从a【1】开始进行输入字符
}

void get_next(STRING L2,int next[])
{
int i=1,j;
j=0;
next[1]=0;
while(i<=L2->length)
{
if(j==0||L2->a[i]==L2->a[j])
{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}

int KMP(STRING L1,STRING L2,int pos,int next[])
{
int i,j,flag=0;
i=pos;
j=1;
while(i<=L1->length&&j<=L2->length)
{
if(j==0||L1->a[i]==L2->a[j])
{
i++;
j++;
}
else
{
j=next[j];
}
}
if(i>L1->a[0])
{
printf("Î′Õòμ½¿éòÔÆ￥ÅäμÄ×Ö·û′®.\n");
exit(-1);
}
else
return  i-L2->a[0];
}

int main()
{
int next[20];
int pos,pos1;
//char ch[20]="abcac";
STRING L1;
STRING L2;
L1=(STRING)malloc(sizeof(string));
L2=(STRING)malloc(sizeof(string));    //这里我定义2个结构，用initstring分别进行初始化，其中一个是模板串，另一个是模式串，但是问题就出在这里，我只能对模板串进行初始化，无法对模式串进行初始化，在进行完L1的初始化后
执行对L2进行初始化的时候就不允许我进行输入，直接一套流程输出下来。返回的值为未知的。求大佬帮看看问题出在哪里。
initstring(L1);
// printf("1\n");
initstring(L2);
get_next(L2,next);

printf("Çëêäèë¿aê¼2éÕòμÄÎ»ÖÃ:");
scanf("%d",&pos);

pos1=KMP(L1,L2,pos,next);

printf("′ó%dÎ»ÖÃ¿aê¼ÎaÆ￥ÅäμÄ.\n",pos1);
}

claws0n · 发表于 2018-10-17 22:03:44

修改指针内容用二级指针

#include <stdio.h>
#include <stdlib.h>
#define max_size 100
typedef struct String
{
char a[max_size];
int length;
}String,*STRING;
void initString(STRING *L) //3õê¼»ˉL
{
int i;
printf("init length:");
scanf("%d",&(*L)->length); //Õa¸öêÇêäèë3¤¶è
printf("start key in char:");
for(i = 1; i <= (*L)->length; i++)
{
scanf("%c",&(*L)->a[i]); //′óa¡¾1¡¿¿aê¼½øDDêäèë×Ö·û
getchar();
}
}
void get_next(STRING *L2,int next[])
{
int i=1,j;
j = 0;
next[1] = 0;
while(i <= (*L2)->length)
{
if(j == 0 || (*L2)->a[i] == (*L2)->a[j])
{
i++;
j++;
next[i] = j;
}
else
j = next[j];
}
}
int KMP(STRING *L1,STRING *L2,int pos,int next[])
{
int i,j,flag = 0;
i = pos;
j = 1;
while(i <= (*L1)->length && j <= (*L2)->length)
{
if(j == 0 || (*L1)->a[i] == (*L2)->a[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
if(i > (*L1)->a[0])
{
printf("KMP\n");
exit(-1);
}
else
return i-(*L2)->a[0];
}
int main()
{
int next[20];
int pos,pos1;
//char ch[20]="abcac";
STRING L1;
STRING L2;
L1=(STRING)malloc(sizeof(String));
L2=(STRING)malloc(sizeof(String));
initString(&L1);
printf("1\n");
initString(&L2);
get_next(&L2,next);
printf("here\n:");
scanf("%d", &pos);
pos1=KMP(&L1,&L2,pos,next);
printf("there\n",pos1);
return 0;
}

复制代码

hhhh还好还好 · 发表于 2018-10-17 23:27:13

claws0n 发表于 2018-10-17 22:03
修改指针内容用二级指针

很感谢你的回复，但是还是没有解决问题，在初始化第二个串的时候还是出错。表现为无法继续输入。

claws0n · 发表于 2018-10-17 23:29:47

hhhh还好还好发表于 2018-10-17 23:27
很感谢你的回复，但是还是没有解决问题，在初始化第二个串的时候还是出错。表现为无法继续输入。

你的还是我的？我加了 getchar() 吸收回车，尤其是循环内用 scanf()，特别敏感

账号		自动登录	找回密码
密码			立即注册

关于KMP算法的一个问题

马上注册，结交更多好友，享用更多功能^_^

浏览过的版块