hdu 1503 最长公共子序列

 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                 else
40                 {
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("
");
59     }
60     return 0;
61 }