Dynamic Programming: Print Longest Common Sub-sequence

Problem Statement:

You are given 2 strings S1 and S2.

You need to print the Longest Common Substring.

Example

Solution

We need to first goto tabular approach by using Bottom Up approach.

Then we start from the last cell.

Then we will check if the characters are equal, we will append the variable to our answer and then we move diagonally upward. “s1[i-1] == s2[j-1], then make L[i][j] = L[i-1][j-1] + 1”

else

we will check which cell has the higher value, if it is the one to the left or to the top. Accordingly we will either decrement the value of i or j. “L[i][j] = max(L[i-1][j], L[i][j-1])”

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_map> 
#include <list> 

using namespace std;

void print_LCS( string str1, string str2 )
{
  int m = str1.size();
  int n = str2.size();

   int L[m+1][n+1];
  
   //fill LCS in bottom up approach
   for (int i=0; i<=m; i++)
   {
     for (int j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;
       else if (str1[i-1] == str2[j-1])
         L[i][j] = L[i-1][j-1] + 1;
       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }
 
   //Length of LCS
   int length = L[m][n];

   char LCS[length+1];
   LCS[length] = '\0'; 
   
   //start from bottom right corner
   int i = m, j = n;
   while (i > 0 && j > 0)
   {
      if (str1[i-1] == str2[j-1])
      {
          LCS[length-1] = str1[i-1]; // if both the string are same, then include that char in the result array
          i--; j--; length--;     // reduce values of i, j and length
      }
      // compare values of L[i-1][j] and L[i][j-1] and go to greater value.
      else if (L[i-1][j] > L[i][j-1])
         i--;
      else
         j--;
   }
 
   //print LCS
   cout << "LCS of " << str1 << " and " << str2 << " is " << LCS<<endl;
}
 

int main()
{
    string str1 = "abcdefg";
    string str2 = "abscdvef";

    print_LCS(str1, str2);

  return 0;
}

Output:

LCS of abcdefg and abscdvef is abcdef