LCS_Reconstruction.cpp

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

int n, m;
string a, b;

int dp[3005][3005];

int rec(int i, int j){
    // return the LCS of a[i...n-1] and b[j...m-1]

    // base case
    if(i >= n || j >= m){
        return 0;
    }

    // memoization
    if(dp[i][j] != -1){
        return dp[i][j];
    }

    // compute
    int ans = 0;

    ans = max(ans, rec(i + 1, j));
    ans = max(ans, rec(i, j + 1));

    if(a[i] == b[j]){
        ans = max(ans, 1 + rec(i + 1, j + 1));
    }

    // save and return
    return dp[i][j] = ans;
}

void generate(int i, int j){
    if(i >= n || j >= m){
        return;
    }

    if(a[i] == b[j]){
        cout << a[i];
        generate(i + 1, j + 1);
    }
    else{
        // use dp instead of rec to avoid extra recursion
        if(dp[i+1][j] >= dp[i][j+1]){
            generate(i + 1, j);
        }
        else{
            generate(i, j + 1);
        }
    }
}

void solve(){
    cin >> a >> b;

    n = a.length();
    m = b.length();

    memset(dp, -1, sizeof(dp));

    rec(0, 0);          // fill dp
    generate(0, 0);     // reconstruct answer
    cout << endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); 
    cout.tie(0);

    solve();
}