Table of Contents
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;
}