Longest Common Subsequence Hackerrank:

Question askedto find the longest common subseq. Technique used-dp,time complexity=O(n^2)

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <stdio.h>
#include <utility>
#include <vector>
// five elements
#include <cstdlib>
#include <iomanip>
#define ll long long
#define ef else if
#define rep(i, s, n) for (ll i = s; i < n; i = i + 1)
#define rev(i, s, n) for (int i = s; i > n; i = i - 1)
using namespace std;
#define fr first
#define se second
#define pb push_back
#define mp make_pair
#define mv vector<ll>
#define vv vector<vector<ll>>
#define vii vector<pair<ll, ll>>
#include <functional>
#include <map>
#include <queue>
#include <set>
// akane_psycho
#define fastio                                                                 \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(NULL);                                                               \
  cout.tie(NULL);
#define c1(a) cout << a << endl;
#define c2(a, b) cout << a << " " << b << endl;
#define c4 (k, x, b, c) printf(" %d %d %d %d ", &k, &x, &b, &c)
#define db double
#define inf 1e18
#define lim 2000000000
#define mo 1000000007
#define MAXN 1000001
#define rp(v)                                                                  \
  cout << endl;                                                                \
  rep(i, 0, v.size()) cout << v[i] << " ";                                     \
  cout << endl;
#define lb(v,val) lower_bound(v.begin(),v.end(),val)-v.begin()
#define ub(v,val) upper_bound(v.begin(),v.end(),val)-v.begin()
#define fill(a,d) memset(a,d,sizeof(a))

ll mod(ll n){
    return n%(ll)mo;
}
int main()
{
    ll t;t=1;while(t--){
        ll n,m,p,q;cin>>n>>m;
        ll dp[n+1][m+1];
        memset(dp,0,sizeof(dp));
        ll x[n+1],y[m+1];
        rep(i,1,n+1)cin>>x[i];
        rep(i,1,m+1)cin>>y[i];
        ll mx=0;
        rep(i,1,n+1){
            rep(j,1,m+1){
                if(x[i]==y[j])
                {dp[i][j]+=(dp[i-1][j-1]+1);
                if(dp[i][j]>mx){
                    mx=dp[i][j];
                    p=i;
                    q=j;
                }
                //mx=max( mx, dp[i][j] );
                }
                else {
                    dp[i][j]=max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        
        mv ans;
        //c2(p,q)
        for(ll i=p;i>=0;i--){//c1(q)
            rep(j,0,q+1){
                if(dp[i][j]>dp[i-1][j] && dp[i][j]==mx ){ans.pb(x[i]);q=j;mx--;break;}
            }
        }
        for(ll i=ans.size()-1;i>=0;i--)cout<<ans[i]<<" ";
        //for(int i=p;i>p-mx;i--)cout<<x[i]<<" ";
        //rep(i, p-mx+1 , p+1)cout<<x[i]<<" ";        
    }
}

Leave a Reply