#include <iostream>#include <stdio.h>#include <string.h>#include <math.h>#include <stdlib.h>#include <algorithm>#include <vector>#include <limits.h>#include <queue>#include <stack>using namespace std;int dp[110][110],cot[110][110],i,j;string a,b,ans,lcs;void push(int i,int j){ if(i == 0||j == 0) return; if(cot[i][j] == 3) { push(i-1,j-1); lcs += a[i-1]; } else if(cot[i][j] == 2) push(i-1,j); else push(i,j-1);}int main(){ while(cin>>a>>b) { int l1 = a.size(); int l2 = b.size(); for(i = 0;i <= l1;i ++) dp[0][i] = 0; for(i = 0;i <= l2;i ++) dp[i][0] = 0; for(i = 1;i <= l1;i ++) { for(j = 1;j <= l2;j ++) { if(a[i-1] == b[j-1]) {dp[i][j] = dp[i-1][j-1] + 1;cot[i][j] = 3;} else if(dp[i-1][j] >= dp[i][j-1]) {dp[i][j] = dp[i-1][j];cot[i][j] = 2;} else {dp[i][j] = dp[i][j-1];cot[i][j]=1;} } } ans = ""; lcs = ""; push(l1,l2); int t; for( i = j = 0,t = 0; t < lcs.size(); ) { if( a[i] == lcs[t] && b[j] == lcs[t] ) cout<<lcs[t],t++,i++,j++; else if( a[i] == lcs[t] ) cout<<b[j++]; else if( b[j] == lcs[t] ) cout<<a[i++]; else cout<<a[i++]<<b[j++]; } while(i < l1)cout<<a[i++]; while(j < l2) cout<<b[j++]; cout<<endl; }}
