Problem :-
Longest Common Subsequence ( LCS ) problem.
Given two sequences, find the longest common subsequence present in both the sequences.
In subsequence, elements of the sequence need not be consecutive.
For e.g, "lgtm" is a subsequence of "algorithms".
Consider two sequences { 1, 2, 3, 2, 4, 1, 2 } & { 2, 4, 3, 1, 2, 1 }
Longest Common Subsequence ( LCS ) is { 2, 3, 2, 1 } of length 4.
Solution :-
Suppose we want to find LCS of two strings ( str1 of size m and str2 of size n )
First, we will characterize the structure of an optimal solution.
Let lcs ( i , j ) denotes the length of LCS till index i of str1 and index j of str2.
There are 2 possibilities :
1 ) if str1 ( i ) == str2 ( j ) , then the problem reduces to finding 1 + lcs ( i - 1 , j - 1 )
2 ) if str1 ( i ) != str2 ( j ) , then the problem reduces to finding maximum of the two overlapping subproblems
[ lcs ( i - 1 , j ) and lcs ( i , j - 1 ) ]
Thus, optimal solution is defined recursively as :
lcs ( i , j ) = 1 + lcs ( i - 1 , j - 1 ) if str1 ( i ) == str2 ( j )
lcs ( i , j ) = max [ lcs ( i - 1 , j ) , lcs ( i , j - 1 ) ] if str1 ( i ) != str2 ( j )
Now, lcs ( i , j ) can be found for any values of i and j.
Eventually, lcs ( m , n ) gives the required solution.
The implementation shown below maintains some additional information to print the actual Longest Common Subsequence apart
from the length of LCS.
#include<iostream>
using namespace std;
// print the Longest common subsequence
void printLCS(int **sequence,int seq1[],int i,int j) {
if(i == 0 || j == 0)
return;
if(sequence[i][j] == 1) {
printLCS(sequence,seq1,i-1,j-1);
cout<<"\t"<<seq1[i-1];
}
else
if(sequence[i][j] == 2)
printLCS(sequence,seq1,i-1,j);
else
printLCS(sequence,seq1,i,j-1);
}
/* find the longest common subsequence of two strings seq1 & seq2
suppose m -> length of seq1 & n -> length of seq2
lcs(i,j) -> LCS till index 'i' of seq1 and index 'j' of seq2
lcs(m,n) -> LCS if seq1 and seq2
Standard Recursive Solution :-
1) lcs(i,j) = lcs(i-1,j-1)+1, if seq1(i) = seq2(j)
2) lcs(i,j) = max[lcs(i,j-1),lcs(i-1,j)], if seq1(i) != seq2(j)
In the actual implementation, we compare seq[i-1] and seq[j-1]
since the array index starts from 0
*/
int findLCS(int seq1[],int m,int seq2[],int n) {
int i,j;
// matrix to hold lcs values
int **lcs;
lcs = new int*[m+1];
for (j=0;j<m+1;j++) {
lcs[j] = new int[n+1];
}
// matrix to trace the actual subsequence
int **sequence;
sequence = new int*[m+1];
for (j=0;j<m+1;j++) {
sequence[j] = new int[n+1];
}
// if one of the sequence is NULL
// lcs = 0 [boundary cases]
for (i=0;i<=m;i++) lcs[i][0]=0;
for (j=0;j<=n;j++) lcs[0][j]=0;
// compute the lcs at each (i,j)
// i -> index of seq1 & j -> index of seq2
// lcs at (m,n) is the final solution
// Values assigned to sequence(i,j) [1/2/3]
// differentiates the three cases as implemented below
// this will be used for tracing the actual LCS
for (i=1;i<=m;i++) {
for (j=1;j<=n;j++) {
if (seq1[i-1] == seq2[j-1]) {
// case1 of standard recursive solution
lcs[i][j] = lcs[i-1][j-1]+1;
sequence[i][j] = 1;
}
// case2 of standard recursive solution
else if (lcs[i-1][j] >= lcs[i][j-1]) {
lcs[i][j] = lcs[i-1][j];
sequence[i][j] = 2;
}
else {
lcs[i][j] = lcs[i][j-1];
sequence[i][j] = 3;
}
}
}
cout<<"\nThe LCS is :-\n";
printLCS(sequence,seq1,m,n);
return lcs[m][n];
}
// main
int main() {
int seq1[] = {1,2,3,2,4,1,2};
int seq2[] = {2,4,3,1,2,1};
int len_seq1 = sizeof(seq1)/sizeof(seq1[0]);
int len_seq2 = sizeof(seq2)/sizeof(seq2[0]);
int len_lcs = findLCS(seq1,len_seq1,seq2,len_seq2);
cout<<"\nLCS length :: "<<len_lcs;
cout<<endl;
return 0;
}