1 /* 2 给两个串a,b。输出一个最短的串(含等于a的子序列且含等于b的子序列) 3 */ 4 #include <iostream> 5 #include <cstdio> 6 #include <cstring> 7 using namespace std; 8  9 const int maxn=105;10 int dp[maxn][maxn],path[maxn][maxn];11 int len,len1,len2;12 char text[maxn],a[maxn],b[maxn];13 14 void getpath()15 {16     int n=len,i=len1,j=len2;17     while(n)18     {19         if(path[i][j]==0)20             text[n--]=a[i],i--,j--;21         else if(path[i][j]==1) i--;22         else j--;23     }24 }25 26 int main()27 {28     int i,j,k;29     a[0]=b[0]=‘0‘;30     while(~scanf("%s%s",a+1,b+1))31     {32         memset(dp,0,sizeof(dp));33         len1=strlen(a)-1,len2=strlen(b)-1;34         for(i=1;i<=len1;i++)35         {36             for(j=1;j<=len2;j++)37             {38                 if(a[i]==b[j])dp[i][j]=dp[i-1][j-1]+1,path[i][j]=0;39                 else40                 {41                     if(dp[i-1][j]>dp[i][j-1]) dp[i][j]=dp[i-1][j],path[i][j]=1;42                     else dp[i][j]=dp[i][j-1],path[i][j]=2;43                 }44             }45         }46         len=dp[len1][len2];47         getpath();48         j=1,k=1;49         for(i=1;i<=len;i++)50         {51             while(a[j]!=text[i]) printf("%c",a[j++]);52             while(b[k]!=text[i]) printf("%c",b[k++]);53             printf("%c",text[i]);54             j++;k++;55         }56         while(j<=len1) printf("%c",a[j++]);57         while(k<=len2) printf("%c",b[k++]);58         printf("\n");59     }60     return 0;61 }