Submission #10405941

---

Source Code Expand

//*******Abhijit Burman***********//
//Jalpaiguri Government Engineering College//

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

#define pb push_back
#define mk make_pair
#define MAXX (1000000000000000000+7)
#define fio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
string temp=" ";
ll dp[3010][3010];
string s,tt,ans="";
ll ii,jj;
//vector<ll> dp(100000100,110);
ll LCS(ll i, ll j)
{

    if(i>ii || j>jj)
    {
        return 0;
    }
   else
    {
        //cout<<i<<" "<<j<<endl;
        if(dp[i][j]!=-1)
        {
            //cout<<"Hello"<<i<<" "<<j<<endl;
            return dp[i][j];
        }
        else
        {

            if(s[i]==tt[j])
            {

                dp[i][j] = 1+LCS(i+1,j+1);
                return dp[i][j];
            }
            else
            {
                dp[i][j] = max(LCS(i+1,j),LCS(i,j+1));
                return dp[i][j];
            }

        }
    }

}

int main( )
{
    fio;

	cin>>s>>tt;
	 ii=s.size()-1;
	 jj=tt.size()-1;
	 memset(dp,-1,sizeof(dp));

//	ll jj;
    //cout<<v.size()<<endl;
    LCS(0,0);
    //ll maxi = 0;
    ll i=0,j=0;
    while(i<=ii && j<=jj)
    {
        if(s[i]==tt[j])
        {
            ans+=s[i];
            i++;
            j++;
        }
        else
        {
            if(dp[i][j] == dp[i+1][j])
            {
                i++;
            }
            else
            {
                j++;
            }
        }
        //cout<<ans<<endl;
    }
    cout<<ans<<endl;
    //cout<<endl;

    return 0;
}

Submission Info

Judge Result