Longest Common Subsequence in C++

By G Ganga Jathin

Finding Longest Common Subsequence (LCS) of two strings using Recursion, Dynamic Programming in C++

We find Longest Common Substring between two strings using Recursion and optimize the code further by eliminating Overlapping Subproblems and Optimal Substructure properties using Dynamic Programming in C++

Here the concept of the code is that We check the last character of two strings if the match we add 1 to the diagonal value of our dp table, if it doesn't match we then take the maximum value of the above and last values in the table, this effectively means that if characters match we add that character to our solution else we take a maximum of two cases by removing the last character of one string then another string and take that maximum value.

The relevant code for the given conceptual idea is below,

for(int i = 1;i <= x;i++)
    {
        for(int j = 1;j <= y;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]);
            maxi = max(maxi,dp[i][j]);
        }
    }

while(a >= 0 && b >= 0)
    {
        if(dp[a][b] == dp[a][b-1])b--;
        else if(dp[a][b] == dp[a-1][b])a--;
        else
        {
            ans += s1[a-1];
            a--;
            b--;
        }
    }

How to use the Code,

1) Download the zip file and extract the source file from it
2) Run it in your Ide of choice
3) Give 2 strings as input to get the longest common subsequence of them