HEU 2013 Advanced Fruits
2012年05月27日
⁄ 综合
⁄ 共 1764字 ⁄ 字号
小 中 大
/**//**************************************
Problem: HEU 2013 Advanced Fruits
Time: 0.0020 s
Memory: 548 k
Accepted Time: 2009-05-08 18:49:38
Tips: 求最大公共子序列，考虑最大值为0时的特殊情况
**************************************/
#include <stdio.h>
#include <string.h>
int main()
{
char a[109],b[109];
int table[109][109];
int aa[109],bb[109];
while(scanf("%s%s",a+1,b+1)!=EOF)
{
int i,j;
int lena=strlen(a+1),lenb=strlen(b+1);
for(i=0;i<=lena;i++)table[0][i]=0;
for(i=0;i<=lenb;i++)table[i][0]=0;
for(i=1;i<=lena;i++)
{
for(j=1;j<=lenb;j++)
{
if(a[i]==b[j])table[i][j]=table[i-1][j-1]+1;
else if(table[i-1][j]>table[i][j-1])table[i][j]=table[i-1][j];
else table[i][j]=table[i][j-1];
}
}
if(table[lena][lenb]==0)printf("%s%s\n",a+1,b+1);
else
{
int ii=0,jj;
i=lena,j=lenb;
while(i!=0&&j!=0)
{
if(table[i][j]==table[i-1][j-1]+1&&a[i]==b[j])
{
aa[ii]=i;
bb[ii]=j;
ii++;
i--,j--;
}
else if(table[i-1][j]>table[i][j-1])i--;
else j--;
}
ii=jj=1;
for(i=table[lena][lenb]-1;i>=0;i--)
{
while(ii!=aa[i])
{
printf("%c",a[ii]);
ii++;
}
while(jj!=bb[i])
{
printf("%c",b[jj]);
jj++;
}
printf("%c",a[ii]);
ii++,jj++;
}
printf("%s%s\n",a+aa[0]+1,b+bb[0]+1);
}
}
return 0;
}