C语言 求最长公共子串的代码,其中有一句j+=length1;不太明白作用是什么,没有这句有什么影响,望解答

2025-02-27 22:28:26
推荐回答(2个)
回答1:

这个算法是错误的,代码中有一些错误,我修改如下:

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+k length1++;
if(length1>length)
{
index=i;
length=length1;
}
j+=length1;//这一句的作用是什么没有这一句对程序有什么影响?×/
}
else j++;
}
i++;
}
for (i=0;i c[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+k length1++;
if(length1>length)
{
index=i;
length=length1;
}
}
j++;
}
i++;
}
for (i=0;i c[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

回答2:

j=j+lenght1;
这会改变j的值.没有的话他一直在查t[0],死循环