回 帖 发 新 帖 刷新版面

主题:请各位大侠帮忙找一下KMP算法小程序的错误,谢啦!

这是数据结构中的KMP算法,但是搜不到模式串。并且经Next函数处理后,不管输入什么模式,next[100]的元素总是0、1、2、3、4、、、、、
请各位大侠帮帮忙改一下
#include<stdio.h>
#include<string.h>
int Next(int next[],char temp[]);
int main(void)
{ int next[100],i=0,j=0,k,l,m,flag=1;
  char temp[100],c[5][100];
  printf("请输入5个字符串");
  for(k=0;k<5;k++)
      gets(c[k]);
  printf("查找:");
  gets(temp);
  l=strlen(temp);
  Next(next,temp);
  while(k<5)
  { m=strlen(c[k]);
    while(i<=m&&j<=l)
    { if(j==0||c[k][i]==temp[j])
    { i++;
      j++;
    }
    else j=next[j];
    }
    if(j>l)
    { printf("找到了:\n%s",c[k]);
      flag=0;
    }
    k++;
  }
     if(flag)
        printf("找不到");
     for(i=0;i<l;i++)
         printf("%d",next[i]);
     getchar();
     getchar();
   return 1;
}

int Next(int next[],char temp[])
{ int i=0,j=0,l;
  l=strlen(temp);
  next[0]=0;
  while(i<l)
  { if(j==0||temp[i]==temp[j])
  {  i++;
     j++;
     next[i]=j;
  }
    else j=next[j];
  }
  return 1;                                                                                    }

回复列表 (共2个回复)

沙发

一次先看一个串吧。一次就比较5个串不好定位错误。
看看你那个next函数。不管怎样if都是true
你希望所有串的下标从什么位置开始呢?
如果从0开始,则一开始next函数中定位主串的下标变量应该初始化为0,字串下标初始话为-1;
如果从1开始,则一开始next函数中定位主串的下标变量应该初始化为1,字串下标初始话为0;

对于你的next函数来说
j = 0的话,i = 1;if应为if(j==0||temp[i]==temp[j])
i = 0的话,j = -1;if应为if(j==-1||temp[i]==temp[j])

去这看看
http://tr0217.blog.163.com/blog/static/3606648020099302426539/

板凳

太感谢了,终于知道错在哪了

我来回复

您尚未登录,请登录后再回复。点此登录或注册