关于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()，特别敏感

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