这个算法是错误的,代码中有一些错误,我修改如下:
j+=length的原始意图是想让s[i]==t[j]满足的情况下,将t字符串移动。
但为什么能一下移动length这么长?这样虽然程序不会死循环,但结果不对。
由于一下子移动太多,可能会漏掉真正的最长公共子串,比如下面这个例子:
#include
#include
void MaxComStr_youError(char s[],char t[],char c[])
{
int index=0,length=0,i,j,k,length1;
i=0;
while(s[i]!='\0')
{
j=0;
while(t[j]!='\0')
{
if(s[i]==t[j])
{
length1=1;
for(k=1 ; i+klength1++;
if(length1>length)
{
index=i;
length=length1;
}
j+=length1;//这一句的作用是什么没有这一句对程序有什么影响?×/
}
else j++;
}
i++;
}
for (i=0;ic[i]=s[index+i];
c[length]='\0';
}
void MaxComStr_OK(char s[],char t[],char c[])
{
int index=0,length=0,i,j,k,length1;
i=0;
while(s[i]!='\0')
{
j=0;
while(t[j]!='\0')
{
if(s[i]==t[j])
{
length1=1;
for(k=1 ; i+klength1++;
if(length1>length)
{
index=i;
length=length1;
}
}
j++;
}
i++;
}
for (i=0;ic[i]=s[index+i];
c[length]='\0';
}
int main(int argc, char* argv[])
{
char s[] = "xxxxxxxxababc";
char t[]= "abababc";
char c[100];
printf("s=%s\r\nt=%s\r\n",s,t);
MaxComStr_youError(s,t,c);
printf("\r\nERROR result:%s\r\n",c);
MaxComStr_OK(s,t,c);
printf("OK result:%s",c);
}
程序输出为:
s=xxxxxxxxababc
t=abababc
ERROR result:abab
OK result:ababc
j=j+lenght1;
这会改变j的值.没有的话他一直在查t[0],死循环