/*                          “There is no secret ingredient”


                                                      .:+++/.`                             
                                                             `/hdmmNmms.                            
                                                             `.-/+sydmmo`                           
                       ./syhys/`                        ````````````-/s/`                           
                      .smmmmdyo-`                   ```.-:+syyyso+:....`                            
                      -dNmho:`    ```````` ``````````.:sdmmNNNNNNmmho:--..``                        
                      -hh+-` ```./+osysss+:`````````.:hNNNNmysyhmNNNmho/:--..`                      
                       -:````./ydmmNNNNNmmmo```````..smNNm+..--.-omNNNmh+/::--.                     
                      ``````:ymmNmho++sdNNNm+ `````..sNNN/.ymmmh+-+mNNNNh+:::::.`                   
                     `.````/dmNNh-`:oso/+mNNs`````...+mNm-oNNNmNd//dMNNNmy::::::-`                  
                    ..````/dmmNh.`ommNmdo/mm/``....---+ydsomNNNmyohNNNNNNd/::::/:-                  
                   `.````.ymmmNs``smNNNmy+mo..```````..:+shdmmmddNNNNNNNNd+-:::///.                 
                  `..````:dmmNNmo--ohdhyyd+.``     `.:+o++ossoshdmmmNNNNdo:-:://++/.`               
                  ..`````/mmmmmNNmhyyhdmd/...+sssooydmNNNy+oo+:..-:/+++/:--:://+o++o/.`             
                 .-.`````-ymmmmNmmNNNNNy:.-.omNNNNNNNNNNmh+osyo-........--::/++ooooyhs-`            
                .--..`````-sdmNNNNNNmh/``.-./dhNNNNNNNmdysosyho:-.....---::/++ooooshddh+.           
              `-+/-...``````-/osyso/-````.::-:/syyhdhsooosyhmhs:--------::/++oosssyhmNNms-`         
            `-oyyo:-...``````````````````.-///::://++/oshdddhss/-------::/++ossssydmNNNNmy:`        
           `/yddhy+:-....`````````````.....-:/ossssyyhhhhys++os+:--:::::/++osssyyhmmNNNNNmh+`       
          .+hmmmdhs/---.......````.....-----...--::::::::::/+sso/::::///++osssyhdmNNNNNNNNmdo-`     
        `:sdmmmmmdhs/:-----.........----:::--....```...-:/+ossys+/////++oossyydmNNNNNNNNNmmmds-`    
       `+hdmmmmmmmdhs+::::-----------::::::::--------::/+ossyyyso+++++oosssyhdmNNNNNNmNmNmNmmms-    
      .oddmmmmmmmmmdhyo///::::::::::::::///////++/+++oossyyyyyyssoooosssyyhdmNNNNNNNNNNmmmmmmmdo`   
     `+hdmmmmmmmmmmmmdhys++//////////////+//++ossyyyyhhhhhhhyyyssssssyyhdmNNNNNNNNNNmmmNmmmmmmmh:   
     :hddmmmmmmmmmmmmmmmdhyyoooo++++++++++++ooossyyhhhhhyyyyyyyyyyyhhdmNNNNNNNNNNNNNNNNNNNNNmmmmy-  
    .yddmmmmmmmmmmmmmmmmmmmmdhyyyssssooooooosooossssssyyyyyhhhddmmNNNNNNNNNNNNNNNNNNNNNNNNNNNmmmms. 
    odmmmmmmmmmmmmmmmmmmNNNmmmmmmddddhhhhyyhyyyyhyyhhhddddmNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNmmmh-`
   .hdmmmmmmmmmmNNmNNNmmNNNNmNNNNNNNNNNNNmmmmmmmmmNNNNNNNNNNNNNNNNNNNNNNmNNNNNNNNNNNNNNNNNNNNNNNmm/`
   :dmmmmmNmmmmmNNNNNNNmmNNNNmmNNNNNNNNNmmmmmmdddhhyyssooo++++++ooosyhdmmmNNNNNNNNNNNNNNNNNNNNNNNm/`
   +dmmmmmmNmNNNNNNNNNNNNNNNNNmmmdhhyso++//::--.....``.......---::/ohmNNmNNNNNNNNNNNNNNNNNNNNNNNNm/`
  `+dmmmmmmmmmNNNNNNNNNNmNNNNNmy+:--...``````````````......----:::/ymNNNNNNNNNNNNNNNNNNNNNNNNNNNmh-`
  `+dmmmmmmmmNNNNNNNNNNNNNNNNNmho:..`````````````........-----::::/+hmNNNNNNNNNNNNNNNNNNNNNNNNNNms. 
   -dmmmmmmmNNNNmNNNNNNNNNNNNmmmho-.`````````````.......-----:::://oydmNNNNNNNNNNNNNNNNNNNNNNNNNd/` 
   `ommmmmNNNNNNNNNmNNNNNNNNNNNNmh+-```````````.........-----:::::+dNNNNNNNNNNNNNNNNNNNNNNNNNNNd+`  
    -hmmmmmmmNNNNNmmmNNNNNNNNNNNmdo/-..`````````........------:::/+hmNNNNNNNNNNNNNNNNNNNNNNNNNdo`   
     :dmmmNmNNNNmNmNmNNNNNNNNNmmdyyso+:.````...........------:::://+hNNNNNNNNNNNNmNNNNNNNNNNmh:`    
     `+hmNNmNNNNNNmNmNNNNNNNNNNNmdysso/-..............------::::///odNNNNNNNNNNNNNNNNNNNNNmd+-`     
       -odmNNNNNNNNNNNNNNNNNNNNNNmyss+/-...........--------:::::///+shdmNNNNNNNNNNNNNNNNmds-`       
         -ymNNNNNNNNNNmNNNNNNNNNmhyss+:-.......-----------:::://///++ooymNNNmddmmmNNNmmNmh:`        
         ./ymNNNNNNNNNNNNNNNNNNNdyysso/:--------------::::::://///+++oossyyyyhhdmNNNNNNNNms+-       
        -ymNNNNNNNNNNNNNNNNNNNmdhyysso+:----------:::::::::://///+++ooossyyyyhdNNNNNNNNNNNNmd/      
       -ymNNNNNNNNNNNNNNNNNNmhhhyyyss+/:::::::::::::::///////+++++ooossssyyhhmNNNNNNNNNNNNNNmh/`    
      `smNNNNNmmdmmmmNNNNNNmddhhhyyyso+//://////////////++++++ooooossssyyyhdmmNNNmNNNmmmNNNNNmy.    
      `/dNNNNmdddmmmmmNNNNNNmddhhyyyysoo+++++/++++++++o+oooooossssssyyyyhdmmNNNNdmNmmmddmmNNNms.    
      .ymmNNdhdmmmmmmmNNNNNNmmddhhhyyssssoooooosooossssssssssyssyyyyyhhdmNNNNNNNdmmmmmmmdhNNNmh-    
       `-omNdddddmmddmNNNNNNNNmmmdhhyyyyyyyyyysyyyyyyyyyyyyyyyyyhhhhdmmNNNNNNNNNmddmmmmmmdNNh:`     
         `ommddddhdNNNNNNNNNNNNNNmhhhhhyhyyhyhhhhhyyhyyyhhhhhhhhhhhhmNNNNNNNNNNNNNNmdddmmmNd/`      
          `/dNNmmNNNNNNNNNNNNNNNmdhhyssoo+++++++++//+///+//++++osyyhdmNNNNNNNNNNNNNNNmNNNmy:`       
            `+hmNNNNNNNNmddhss+/---.```                          ```.:/+oyhdhdNNNNNNNNNds/`         
              `..-:::---...```                                          ``````.-:::::-.`         */ 


  #include <bits/stdc++.h>
  #define endl "\n"
  #define ll long long int
  #define vi vector<int>
  #define vll vector<ll>
  #define vvl vector < vll >
  #define pii pair<int,int>
  #define pll pair<long long, long long>
  #define mod 1000000007
  #define inf 1000000000000000001;
  #define all(c) c.begin(),c.end()
  #define mp(x,y) make_pair(x,y)
  #define mem(a,val) memset(a,val,sizeof(a))
  #define pb push_back
  #define f first
  #define se second
  
  using namespace std;
  int main()
  {
    std::ios::sync_with_stdio(false);
    ll n=0,m=0,k=0,x=0,t1=0,t2=0,t3=0,f=0,sum=0,count=0;

    string s,t; cin>>s>>t;
    n=s.length();
    m=t.length();

    vector<vector<int>>dp(n+1,vi(m+1,0));
    vector<vector<int>>choice(n+1,vi(m+1,0));

    dp[0][0]=0;

    for (ll i = 1; i < n+1; ++i)
    {
      for (ll j = 1; j < m+1; ++j)
      {
        // exclude the current element
        dp[i][j]=dp[i-1][j];
        choice[i][j]=0;

        if(dp[i][j-1]>dp[i][j]){
          choice[i][j]=1;
          dp[i][j]=dp[i][j-1];
        }
        
        // if the characters are same
        if(s[i-1]==t[j-1]){
          dp[i][j]=max(dp[i][j],1+dp[i-1][j-1]);
          choice[i][j]=2;
        }
      }
    }

    string lcs;
    ll i=n,j=m;

    while(i>=0 && j>=0){
      if(choice[i][j]==0)
        i--;
      else if(choice[i][j]==1)
        j--;
      else{
        lcs.pb(s[i-1]);
        i--; j--;
      }
    }

    reverse(all(lcs));

    cout<<lcs;


    return 0;
  }

Measured memory_bytes: 73612