23 Printing Longest common subsequence

23. Printing Longest common subsequence

https://youtu.be/x5hQvnUcjiM
Article Link of GFG : https://www.geeksforgeeks.org/printing-longest-common-subsequence/

--------------------------xxxxxxxxxxxxxxx---------------xxxxxxxxxxxxx   CODE     xxxxxxxxxxxxxxx-----------------------xxxxxxxxxxxxxxxxxxx------

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

string LCS(string s1, string s2, int n, int m) {
    
    string ans = "";
    
	int dp[n + 1][m + 1]; // DP - matrix

// initialising the table 

	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++)
			if (i == 0 || j == 0)
				dp[i][j] = 0;

// filling the table 

	for (int i = 1; i <= n; i++)
	
		{
		    
		    for (int j = 1; j <= m; j++)
		  {
               //if characters are matching  
			if (s1[i - 1] == s2[j - 1]) 
				dp[i][j] = 1 + dp[i - 1][j - 1];
				
	           //  if characters aren't matching
			else 
				dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
		    
	      }
		    
		}

	int i = n, j = m;
	
	while (i > 0 && j > 0) {
		if (s1[i - 1] == s2[j - 1]) {
			ans += s1[i - 1];
			i--, j--;
		}
		else {
			if (dp[i][j - 1] > dp[i - 1][j])
				j--;
			else
				i--;
		}
	}
	reverse(ans.begin(), ans.end());

	return ans;
}

signed main() {
	string s1, s2;
	cin >> s1 >> s2;
	int n = s1.length(), m = s2.length();

	cout << LCS(s1, s2, n, m) << endl;
	return 0;
}