#include <iostream> #include <string.h> using namespace std; const int N = 102; char a[N], b[N]; int dp[N][N]; int map[N][N]; void printLCS(int i,int j) { if(i==0&&j==0) return; if(i==0) { printLCS(i,j-1); printf("%c",b[j-1]);//输出x,y时下标要减1,因为在记b(方向)的时候是从1开始的; return; } else if(j==0) { printLCS(i-1,j); printf("%c",a[i-1]); return; } if(map[i][j]==0) { printLCS(i-1,j-1); printf("%c",a[i-1]); } else if(map[i][j]==1) { printLCS(i-1,j); printf("%c",a[i-1]); } else { printLCS(i,j-1); printf("%c",b[j-1]); } } int main() { while(cin >> a >> b) { int alen = strlen(a); int blen = strlen(b); memset(dp, 0, sizeof(dp)); for(int i = 1; i <= alen; i++) { for(int j = 1; j <= blen; j++) { if(a[i - 1] == b[j -1]) { dp[i][j] = dp[i-1][j-1] + 1; map[i][j] = 0; //xiexia } else { if(dp[i][j-1] > dp[i-1][j]) { dp[i][j] = dp[i][j-1]; map[i][j] = 2;//you } else { dp[i][j] = dp[i-1][j]; map[i][j] = 1; //xia } } } } int L = dp[alen][blen]; if(L == 0) { cout << a << b << endl; continue; } int cnt = 0; int x = alen; int y = blen; char com[N]; memset(com, 0, sizeof(com)); /*while(cnt < L) { if(map[x][y] == 0) { com[cnt++] = a[x-1]; x = x -1; y = y -1; } else if(map[x][y] == 1) x = x -1; else y = y - 1; }*/ printLCS(alen, blen); cout << endl; } return 0; }