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

Back | Next