Print Longest common subsequence

Given two strings s1 and s2, write a function that will find the longest subsequence present in both of them subsequence is sequence of the elements which may not be in continous but should be in same relative order

Example

INPUT
s1 = “abcde”
s2 = “bdgek”

OUTPUT
LCS is “bde”

Algorithm

1. Build L[m+1][n+1], where L[i][j] contains length of LCS of s1[0…i-1] and s2[0…j-1]

a. Simply run two loops, outer loop variable i, inner loop variable j
b. For each character in s1(outer loop) select all the characters in s2(inner loop)
c. If  i == 0 and j == 0, then make L[i][j] =0 //Base case
d. If s1[i-1] == s2[j-1], then make L[i][j] = L[i-1][j-1] + 1
e. else, L[i][j] = max(L[i-1][j], L[i][j-1])

L[][] for above example.

2. As we can see L[m][n] contains the length of the longest common subsequence. create a character array LCS[] to print the longest common subsequence

3. Traverse the array L[m][n]

a. if s1[i-1] == s2[j-1], then include this character in LCS[]
b. else, compare values of L[i-1][j] and L[i][j-1] and go in direction of greater value.

C++ Program

#include <bits/stdc++.h>
using namespace std;
 
//Prints the Longest common subsequence
void printLCS( char *s1, char *s2, int m, int n )
{
   int L[m+1][n+1];
 
   //Building L[m][n] as in algorithm
   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 (s1[i-1] == s2[j-1])
         L[i][j] = L[i-1][j-1] + 1;
       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }
 
   //To print LCS
   int index = L[m][n];
   //charcater array to store LCS
   char LCS[index+1];
   LCS[index] = '\0'; // Set the terminating character
   
   //Stroing characters in LCS
   //Start from the right bottom corner character
   int i = m, j = n;
   while (i > 0 && j > 0)
   {
      //if current character in s1 and s2 are same, then include this character in LCS[]
      if (s1[i-1] == s2[j-1])
      {
          LCS[index-1] = s1[i-1]; // Put current character in result
          i--; j--; index--;     // reduce values of i, j and index
      }
      // compare values of L[i-1][j] and L[i][j-1] and go in direction of greater value.
      else if (L[i-1][j] > L[i][j-1])
         i--;
      else
         j--;
   }
 
   // Print the LCS
   cout << "LCS of " << s1 << " and " << s2 << " is "<<endl << LCS<<endl;
}
 
/* Driver program to test above function */
int main()
{
  char s1[] = "abcde";
  char s2[] = "bdgek";
  printLCS(s1, s2, strlen(s1), strlen(s2));
  return 0;
}

Try It

 

Translate »