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

Submitted by G Ganga Jathin (GangaJathin)

- Steganography in Python
- convert XML to json in Java
- Simple library system using classes using Python
- Generate One-time-password (OTP) using Java
- Love-Calculator-in-Python
- How to get specific element from the XORinacci Series in minimum time complexity in Java
- Travelling Salesman Problem using AI Genetic Algorithm in C++
- Basic Calculator using Tkinter in Python

Download packets of source code on Coders Packet

## Comments