#include<bits/stdc++.h>
//#include<conio.h>
using namespace std;

#define ff first
#define ss second
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
#define mp make_pair
#define endl "\n"      // Comment in INTERACTIVE(there just use endl which flushes output , no need of fflush(sdtout)).
//  for counting setbits -> __builtin_popcountll(x)
// for counting zerobits -> __builtin_ctzll(x)
#define fastio() ios_base::sync_with_stdio(false);        cin.tie(NULL); //(unties i/o buffer).
            // DON'T USE SCANF/PRINTF WITH IT (c/c++ -> seperates buffer).

const int mod = 1000000007;
 const int N = 3000 + 2;
 int dp[N][N];
 int memo[N][N];
 char s1[3001] , s2[3001];
    

 int lcsmemo(int i,int j){
    if(!i || !j)
        return 0;
    if(memo[i][j] != -1)
        return memo[i][j];

    memo[i][j] = max(lcsmemo(i - 1,j), lcsmemo(i,j  - 1));
    if(s1[i -1] == s2[j - 1])
        memo[i][j] = max(lcsmemo(i-1,j - 1) + 1, memo[i][j]);
    return memo[i][j];
 }

int32_t main(){
    fastio()

     // ***** AC_chahiye EK BAR MEIN

     // BEGIN CODE HERE
     memset(memo, -1, sizeof(memo));
    cin>>s1>>s2;

    int l1 = strlen(s1);
    int l2 = strlen(s2);

    // * Global var , initialised with 0.
    // for(int i = 0;i <= l1; ++i)
    //     dp[i][0] = 0;
    // for(int i = 0;i <= l2; ++i)
    //     dp[0][i] = 0;
    
    /* Here want lcs , 
        brute force - compare all subsequence pairs (2^n * 2^m * max(m,n))

        so first optimize recurisvely , want SAME CHAR PAIRS in both
        Start from one side (front/back) , if get SAME TAKE , ELSE DELETE FROM ONE OF THEM.
        complexity -> 2 ^ (m+n) *(not tight) , as in each turn 1 char from one of string is removed.

        optimize above using  dp (memo / bottom - up).
    */

    for(int i = 1;i <= l1; ++i){
        for(int j = 1;j <= l2; ++j){
        	// This is more refined approach , LATER ONE MORE RAW AND EASY TO THINK.
            // if(s2[j - 1] == s1[i - 1])
            //     dp[i][j] = dp[i - 1][j - 1] + 1;
            // else
            //     dp[i][j] = max(dp[i][j -1], dp[i - 1][j]);
        	dp[i][j] = max(dp[i][j -1], dp[i -1][j]);  // Leave 1 char (from both)
        	if(s1[i-1] == s2[j -1])
        		dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);  // if equal , try i-1,j-1
        }
    }

    // ** dp[i-1][j] and dp[i][j-1] WILL HAVE MAX DIFF OF 1 (as only one char change)
    // if s1[i -1] == s2[j -1] , then can remove BOTH+1 / REMOVE from any 1 (both code in dp loop correct).
    //cout<<dp[l2][l1];

    // Building the lcs using dp table (can also * SEPERATE KEEP TABLE).

    // cout<<dp[l1][l2]<<"         "<<lcsmemo(l1,l2)<<endl;

    char str1[3001];
    int l = lcsmemo(l1,l2);
    str1[l] = 0;
    int i = l1 , j = l2;
    while(i && j){  
        if(s1[i - 1] == s2[j-1]){         // if have same char , taken.
            str1[--l] = s1[i - 1];
            i--;  j--;
        }
        else if(memo[i][j - 1]  > memo[i - 1][j])
            j--;     // GOT ANSWER FROM I , J-1 ; so decrease it.
        else
            i--;
    }
    cout<<str1<<endl;
    

    // char str[3001];
    // l = dp[l1][l2];
    // str[l] = 0;
    // i = l1 , j = l2;
    // while(i && j){  
    //     if(s1[i - 1] == s2[j-1]){         // if have same char , taken.
    //         str[--l] = s1[i - 1];
    //         i--;  j--;
    //     }
    //     else if(dp[i][j - 1]  > dp[i - 1][j])
    //         j--;     // GOT ANSWER FROM I , J-1 ; so decrease it.
    //     else
    //         i--;
    // }
    // cout<<str<<endl;
    
    //getch();
}


Measured memory_bytes: 141440