This is a C++ Program that Solves Longest common subsequence using Dynamic Programming technique.

There are 2 strings str1 and str2. Find the length of the longest subsequence common to both str1 and str2.

This problem can be solved using dynamic programming. First we will calculate the length of longest common subsequence for a prefix of str1 and str2. Then, we will tabulate these values in a matrix and use these values to calculate the value of LCS for longer prefixes of str1 and str2.

Time complexity – O(len1*len2)

Case-1:

str1="abcda" str2="bdabac" LCS=3 given by the subsequence "abc"

Case-2:

str1="sbbksg" str2="bpkpsjg" LCS=4 given by the subsequence "bksg"

Case-3:

str1="classical" str2="musical" LCS=5 given by subsequence "sical"

Here is source code of the C++ Program to Solve Longest common subsequence. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

`#include<iostream>`

`#include<string>`

using namespace std;

int longestCommonSubsequece(string str1, string str2, int len1, int len2)

`{`

int i, j;

`//create a matrix of order (len1+1)*(len2+1) to tabulate values`

int LCS[len1+1][len2+1];

`//LCS[i][j]=Length of longest common subsequence of str1[0....(i-1)] and str2[0...(j-1)]`

`//initializing`

for(i=0;i<=len1;i++)

LCS[i][0]=0; //empty str2

for(j=0;j<=len2;j++)

LCS[0][j]=0; //empty str1

`//now, start filling the matrix row wise`

for(i=1;i<=len1;i++)

`{`

for(j=1;j<=len2;j++)

`{`

`//if current character of both strings match`

if(str1[i-1]==str2[j-1])

`{`

LCS[i][j]=1+LCS[i-1][j-1];

`}`

`//mismatch`

`else`

`{`

LCS[i][j]=max(LCS[i-1][j],LCS[i][j-1]);

`}`

`}`

`}`

`//now, return the final value`

return LCS[len1][len2];

`}`

int main()

`{`

`string str1,str2;`

cout<<"Enter first string ";

getline(cin, str1);

cout<<"Enter second string ";

getline(cin, str2);

int len1=str1.length(); //length of str1

int len2=str2.length(); //length of str2

cout<<"Length of longest common subsequence is "<<longestCommonSubsequece(str1,str2,len1,len2);

cout<<endl;

return 0;

`}`

In the main function, we will take input for str1 and str2. We will pass these to the function longestCommonSubsequence as parameters. This function will calculate the result using bottom up DP and return the value which is displayed on the standard output.

Case-1: $ g++ lcs.cpp $ ./a.out Enter first string classical Enter second string musical Length of longest common subsequence is 5

**Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.**

To practice all Dynamic Programming Problems, __here is complete set of 100+ Problems and Solutions__.