Printing Longest common Subsequence.

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

void lcs(string s, string t) {
    
int m=s.size();

int n=t.size();

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

for(int i=1;i<=m;i++)
{
    for(int j=1;j<=n;j++)
    {
      if(s[i-1]==t[j-1])
      dp[i][j]=1+dp[i-1][j-1];
      else
      {
          dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
      }

    }
}

int len=dp[m][n];

string ans="";

for(int i=0;i<len;i++)
ans+='$';

int idx=len-1;


int i=m,j=n;

while(i>0 && j>0)
{
    if(s[i-1]==t[j-1]){
    ans[idx]=s[i-1];
    
    idx--;
    
    i--;
    j--;
    }
    
    else if(dp[i-1][j]>dp[i][j-1])
    i--;
    
    else
    j--;
    
}



	cout<<ans<<" "<<endl;
}