Competitive_Programming/atcoder/dp/F.cpp at master · nishitsharma03/Competitive_Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//#pragma GCC optimize "trapv"
#include<bits/stdc++.h>
#define ll long long int
#define fab(a,b,i) for(int i=a;i<b;i++)
#define pb push_back
#define db double
#define mp make_pair
#define endl "\n"
#define f first
#define se second
#define all(x) x.begin(),x.end()
#define MOD 1000000007
#define quick ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
string s,t;
ll dp[4000][4002];
ll recurse(ll sptr,ll tptr)
{
	if(sptr<0)
		return 0;
	if(tptr<0)
		return 0;
	if(dp[sptr][tptr]!=-1)
		return dp[sptr][tptr];
	if(s[sptr]==t[tptr])
		return dp[sptr][tptr]=recurse(sptr-1,tptr-1)+1;
	else


		return dp[sptr][tptr]=max(recurse(sptr-1,tptr),recurse(sptr,tptr-1));

}
int main()
{ quick;

    cin>>s>>t;
    fab(0,s.size(),i)
    fab(0,t.size(),j)
    {
    	//cout<<dp[i][j];
    	dp[i][j]=-1;

    }

    ll sptr=s.size()-1,tptr=t.size()-1;
    ll siz=recurse(sptr,tptr);
    sptr=s.size()-1;tptr=t.size()-1;
    string ans="";
    while(sptr>=0 and tptr>=0)

    {
    	if(s[sptr]==t[tptr])
    		{ans=s[sptr]+ans;
    			sptr--;
    			tptr--;}
    	else if(sptr>0 and tptr>0 and dp[sptr-1][tptr]>dp[sptr][tptr-1])
    		sptr--;
    	else if(tptr==0)
    		sptr--;
    	else
    		tptr--;


    }
    //assert(ans.size()==siz);
    cout<<ans<<endl;


	return 0;
}