和算法书上讲的那个最大公共了串是一样的。 一开始tl了几次。因为忘记d[i][j]=0的这种情况了！ f[i][j]保存的是a的前i个字符和b的前j个字符的最大子串。 d[i][j]保存的是最大值是如何得来的。d[i][j]=0表示到目前为止还没有相同的子串 d[i][j]=1表示a[i]==b[j] d[i][j]=2表示从左得来 d[i][j]=3表示从上得来  #include<stdio.h>#include<iostream>#include<string.h>int f[105][105];int d[105][105];using namespace std;int main(){ int len1,len2,i,j,len; char a[105],b[105]; char c[210];  while(scanf("%s%s",a,b)!=EOF) {  len1=strlen(a);  len2=strlen(b);  for(i=0;i<len2;i++)//初始条件  {   if(a[0]==b[i])   {    f[0][i]=1;    d[0][i]=1;    for(i++;i<len2;i++)    {     f[0][i]=1;     d[0][i]=2;    }    break;   }   else{ f[0][i]=0;d[0][i]=0;}  }  for(i=0;i<len1;i++)  {   if(a[i]==b[0])   {    f[i][0]=1;    d[i][0]=1;    for(i++;i<len1;i++)    {     f[i][0]=1;     d[i][0]=3;    }    break;   }   else   {    f[i][0]=0;d[i][0]=0;   }  }  for(i=1;i<len1;i++)   for(j=1;j<len2;j++)   {    if(a[i]==b[j])    {     f[i][j]=f[i-1][j-1]+1;     d[i][j]=1;    }    else if(f[i-1][j]>f[i][j-1])    {     f[i][j]=f[i-1][j];     d[i][j]=3;    }    else    {      f[i][j]=f[i][j-1];     d[i][j]=2;    }   }  c[205]='\0';  len=204;  i=len1-1;  j=len2-1;     while(i>=0&&j>=0)    {     if(d[i][j]==1)     {      c[len--]=a[i];      i--;j--;          }     else if(d[i][j]==2)     {      c[len--]=b[j];      j--;     }     else if(d[i][j]==3)     {      c[len--]=a[i];      i--;     }     else if(d[i][j]==0)     {      c[len--]=b[j];      c[len--]=a[i];      i--;      j--;     }    }    while(i>=0)    {     c[len--]=a[i];     i--;    }    while(j>=0)    {     c[len--]=b[j];     j--;    }    printf("%s\n",&c[len+1]);  } return 0;}

评论