Dynamic Programming
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; }