Longest Common Subsequence using Dynamic Programming

«
»

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

Problem Description

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

Problem Solution

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)

Expected Input and Output

Case-1:

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

Case-2:

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
str1="sbbksg"
str2="bpkpsjg"
 
LCS=4 given by the subsequence "bksg"

Case-3:

str1="classical"
str2="musical"
 
LCS=5 given by subsequence "sical"
Program/Source Code

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.

  1. #include<iostream>
  2. #include<string>
  3.  
  4. using namespace std;
  5.  
  6. int longestCommonSubsequece(string str1, string str2, int len1, int len2)
  7. {
  8.     int i, j;
  9.  
  10.     //create a matrix of order (len1+1)*(len2+1) to tabulate values
  11.     int LCS[len1+1][len2+1];
  12.  
  13.     //LCS[i][j]=Length of longest common subsequence of str1[0....(i-1)] and str2[0...(j-1)] 
  14.  
  15.     //initializing
  16.     for(i=0;i<=len1;i++)
  17.         LCS[i][0]=0;    //empty str2
  18.  
  19.     for(j=0;j<=len2;j++)
  20.         LCS[0][j]=0;   //empty str1
  21.  
  22.     //now, start filling the matrix row wise
  23.     for(i=1;i<=len1;i++)
  24.     {
  25.         for(j=1;j<=len2;j++)
  26.         {
  27.             //if current character of both strings match
  28.             if(str1[i-1]==str2[j-1])
  29.             {
  30.                 LCS[i][j]=1+LCS[i-1][j-1];
  31.             }
  32.  
  33.             //mismatch
  34.             else
  35.             {
  36.                 LCS[i][j]=max(LCS[i-1][j],LCS[i][j-1]);
  37.             }
  38.         }
  39.     }
  40.  
  41.     //now, return the final value 
  42.     return LCS[len1][len2];
  43.  
  44. }
  45.  
  46.  
  47. int main()
  48. {
  49.     string str1,str2;
  50.  
  51.     cout<<"Enter first string   ";
  52.     getline(cin, str1);
  53.  
  54.     cout<<"Enter second string   ";
  55.     getline(cin, str2);
  56.  
  57.     int len1=str1.length();  //length of str1 
  58.     int len2=str2.length();  //length of str2 
  59.  
  60.     cout<<"Length of longest common subsequence is "<<longestCommonSubsequece(str1,str2,len1,len2);
  61.  
  62.     cout<<endl;
  63.     return 0;
  64. }
Program Explanation

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.

advertisement
Runtime Test Cases
 
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.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.