Longest Common Subsequence using Dynamic Programming

In this CPP tutorial, we are going to discuss how to find the length of a maximum common subsequence of two strings. Finding the Longest Common Subsequence using Dynamic Programming will be a much better practice for us.

What is Subsequence?

A Sub-sequences is a sequence that appears in same relative order, but not necessarily contiguous.

for example :-  ‘a’, ‘b’, ‘c’, ‘ab’, ‘bc’, ‘abc’ are some Sub-sequence of string “abc”.

Why Dynamic Programming?

We can solve the same problem by simple recursive method but time complexity for this approach is exponential. In the worst case, it will be O ( 2^n ). Instead of calculating for the same sub-problem, again and again, we prefer to use a dynamic programming approach and store the result of every sub-problem which reduces the time complexity into linear.

Algorithm to find Longest Common Subsequence in C++

• Input two strings S1, S2 of length m and n whose sub-sequence to be found.
• Now, fill up the table dp[m+1][n+1] in bottom-up manner.
• If character of both string matches then fill the value in dp[][] table by 1+(dp[][] value in previous diagonal )

dp[i][j] = 1+dp[i-1][j-1]

•  if character of both strings does not matches then, fill the value in dp[][] table as maximum of left or upper value in dp[][] table.

dp[i][j] = max ( dp[i-1][j], dp[i][j-1] )

• Now, value in dp[m][n] stores our result for longest common sub-sequence of string S1, S2.

   C++ Code to find the longest common subsequence of two strings

#include<bits/stdc++.h>

#define for(i,a,b) for(int i=a;i<b;i++)

using namespace std;

typedef long long ll;


      void solve(string s1, string s2, ll m, ll n)
   {
     int dp[m+1][n+1];
       
       for(i,0,m+1)
       {
             for(j,0,n+1)
           {
               if (i == 0 || j == 0) 
                 dp[i][j] = 0; 
   
               else if(s1[i-1]==s2[j-1])
                dp[i][j]=1+dp[i-1][j-1];
               
                else
                  dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
           }
       }
       
       cout<<dp[m][n]<<endl;
   }

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

Input 

Codespeedy

Codersite

OUTPUT

6

As the longest common sub-sequence among the above two input strings is Codese.

also, learn:

• Maximum size Square sub-with all 1’s in C++
• Subset Sum Problem using DP in C++