lcs.cpp

#include <bits/stdc++.h>
using namespace std;
string getLCS(vector<vector<int>> dp, string s1, string s2)
{
  string ans = "";
  int i = s1.length(), j = s2.length();
  while (i > 0 && j > 0)
  {
    if (dp[i][j] == dp[i - 1][j])
      i--;
    else if (dp[i][j] == dp[i][j - 1])
      j--;
    else
    {
      ans = s1[i - 1] + ans;
      i--;
      j--;
    }
  }
  return ans;
}

void print(vector<vector<int>> vec)
{
  for (int i = 0; i < vec.size(); i++)
  {
    for (int j = 0; j < vec[i].size(); j++)
    {
      cout << vec[i][j] << "  ";
    }
    cout << endl;
  }
}

int main()
{
  string s1, s2;
  cout << "Enter first string: ";
  cin >> s1;
  cout << "Enter second string: ";
  cin >> s2;
  int l1 = s1.length(), l2 = s2.length();
  vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1, 0));
  for (int i = 1; i <= l1; i++)
  {
    for (int j = 1; j <= l2; j++)
    {
      if (s1[i - 1] == s2[j - 1])
      {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      }
      else
      {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  cout << "\nLength of longest common subsequence is: " << dp[l1][l2] << endl;
  cout << "\nLongest common subsequence is: " << getLCS(dp, s1, s2) << endl
       << endl;
  cout << "DP Table:\n";
  print(dp);
  return 0;
}