1 //Accepted    208K    0MS 2 //dp 3 //最长公共子序列+路径 4 #include <cstdio> 5 #include <cstring> 6 #include <iostream> 7 using namespace std; 8 const int imax_n = 105; 9 const int inf = 100000000;10 int dp[imax_n][imax_n];11 char s1[imax_n],s2[imax_n];12 int l1,l2;13 int max(int a,int b)14 {15     return a>b?a:b;16 }17 void Dp()18 {19     memset(dp,0,sizeof(dp));20 21     for (int i=1;i<=l1;i++)22     {23         for (int j=1;j<=l2;j++)24         {25             //dp[i][j]=inf;26             dp[i][j]=max(dp[i-1][j],dp[i][j-1]);27             if (s1[i-1]==s2[j-1])28             dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);29         }30     }31     //printf("%d\n",dp[l1][l2]);32 }33 void output(int i,int j)34 {35     if (dp[i][j]==0)36     {37         for (int k=1;k<=i;k++)38         printf("%c",s1[k-1]);39         for (int k=1;k<=j;k++)40         printf("%c",s2[k-1]);41         return ;42     }43     if (dp[i][j]==dp[i-1][j-1]+1 && s1[i-1]==s2[j-1])44     {45         output(i-1,j-1);46         printf("%c",s1[i-1]);47         return ;48     }49     if (dp[i][j]==dp[i-1][j])50     {51         output(i-1,j);52         printf("%c",s1[i-1]);53         return ;54     }55     if (dp[i][j]==dp[i][j-1])56     {57         output(i,j-1);58         printf("%c",s2[j-1]);59         return ;60     }61 }62 int main()63 {64     while (scanf("%s%s",s1,s2)!=EOF)65     {66         l1=strlen(s1);67         l2=strlen(s2);68         Dp();69         output(l1,l2);70         printf("\n");71     }72     return 0;73 }