标题:我的KMP错在哪里呢
取消只看楼主
企鹅
Rank: 1
等 级:新手上路
帖 子:93
专家分:0
注 册:2006-7-14
 问题点数:0 回复次数:6 
我的KMP错在哪里呢
写kmp有个疑问

#include <iostream>
using namespace std;

void get_next(char *c,int *i);
int Index_KMP(char* s,char* T,int pos);

int main()
{
char c[100],d[100];
int b[100];
scanf("%s %s",c,d);
int i,j;
i=Index_KMP(c,d,1);
printf("i=%d\n",i);
return 0;
}

void get_next(char *c,int *next)
{
int i,len,j;
next[0]=-1;
i=0;
j=-1;
len=strlen(c);
while(i<len-1)
{
if(j==-1||c[i]==c[j])
{
i++;
j++;
next[i]=j;
}
else j=next[j];
}
}

int Index_KMP(char* s,char* T,int pos)
{
int j=0,i=0,*p;
p=new int[strlen(T)];
get_next(T,p);
j=0;
while((j!=strlen(T))&&(i!=strlen(s)))
//while((j<strlen(T))&&(i<strlen(s)))
{
if(j==-1)
{
i++;
j++;
}
else if(T[j]==s[i])
{
i++;
j++;
}
else
j=p[j];
}
if(j==strlen(T))
return i-strlen(T)+1;
return -1;
}

为什么用第二个while 会发生错误啊 希望有人可以看看

搜索更多相关主题的帖子: KMP 
2007-10-12 19:10
企鹅
Rank: 1
等 级:新手上路
帖 子:93
专家分:0
注 册:2006-7-14
得分:0 
回复:(永夜的极光)感觉上没错

可是运行的时候就错了啊

2007-10-12 19:19
企鹅
Rank: 1
等 级:新手上路
帖 子:93
专家分:0
注 册:2006-7-14
得分:0 

啊。是如果用红色的子的那个句子就会出错了。上边的代码是我改对了。我不知道这两个句子有什么不同。
我是在VS2005的环境下的

2007-10-12 21:21
企鹅
Rank: 1
等 级:新手上路
帖 子:93
专家分:0
注 册:2006-7-14
得分:0 

是结果不对啊。无论输入什么东西。都返回-1

2007-10-12 23:19
企鹅
Rank: 1
等 级:新手上路
帖 子:93
专家分:0
注 册:2006-7-14
得分:0 

谢谢!

2007-10-14 07:47
企鹅
Rank: 1
等 级:新手上路
帖 子:93
专家分:0
注 册:2006-7-14
得分:0 

明白了

2007-10-14 07:55
企鹅
Rank: 1
等 级:新手上路
帖 子:93
专家分:0
注 册:2006-7-14
得分:0 
回复:(coachard)我好久以前写的,你对比下(下标从...

#include <iostream>
using namespace std;

void get_next(char *c,int *i);
int Index_KMP(char* s,char* T,int pos);

int main()
{
char c[100],d[100];
int b[100];
scanf("%s %s",c,d);
int i,j;
i=Index_KMP(c,d,1);
printf("i=%d\n",i);
return 0;
}

void get_next(char *c,int *next)
{
int i,len,j;
next[0]=-1;
i=0;
j=-1;
len=strlen(c);
while(i<len-1)
{
if(j==-1||c[i]==c[j])
{
i++;
j++;
next[i]=j;
}
else j=next[j];
}
}

int Index_KMP(char* s,char* T,int pos)
{
int j=0,i=0,*p;
p=new int[strlen(T)];
get_next(T,p);
j=0;
//while((j!=strlen(T))&&(i!=strlen(s)))
int lent=strlen(T);
int lens=strlen(s);
while((j<lent)&&(i<lens))
{
if(j==-1)
{
i++;
j++;
}
else if(T[j]==s[i])
{
i++;
j++;
}
else
j=p[j];
}
if(j==strlen(T))
return i-strlen(T)+1;
return -1;
}

你能帮我解释一下为什么这样就可以了么 谢谢!

2007-10-14 08:07



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-177119-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.569918 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved