Longest Common Subsequence

Given two sequences,the task is to find the length of longest sub-sequence present in both of them. A sub-sequence is a sequence that appears in the same relative order, but not necessarily contiguous.For example- “abc”,”fit”,”abfi”,etc are sub-sequences of “abcfit”.A string of length n has 2^n different possible sub-sequences.

Example-

String 1- “BATTING” Length-7
String 2- “BOWLING” Length-7

Longest Common Sub-sequence- “BING” Length-4

Brute Force-

Generate all sub-sequences of both given sequences and find the longest matching sub-sequence.It has an exponential time complexity.

Efficient Algorithm-
lcs(i,j)=
              if (X[i]==Y[j])
             1+lcs(i-1,j-1)
              else
              max(lcs(i-1,j),lcs(i,j-1))

where X[],Y[] are strings.

Recursive Solution-


//char X[0,1...m-1],Y[0,1,...n-1] contains the strings
//lcs(m,n) is called initially.

int lcs(int a,int b)
{
   if (a == 0 || b == 0)
     return 0;

   if (X[a-1] == Y[b-1])
     return 1 + lcs(a-1,b-1);
   else
     return max(lcs(a,b-1), lcs(a-1,b));
}

This problem has overlapping as well as optimal substructure property.Thus,dynamic programming can be applied.A temporary array L[ ][ ] is constructed to store the intermediate results.

DP solution-


int lcs(int m,int n)
{
   int L[m+1][n+1];
   int i,j;
 
// L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] 

   for (i=0; i<=m; i++)
   {
     for (j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;
 
       else if (X[i-1] == Y[j-1])
         L[i][j] = L[i-1][j-1] + 1;
 
       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }
   
//L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] 

   return L[m][n];
}
 

This program has a time complexity of O(m*n) where m,n are lengths of the string which is much better than exponential time complexity.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

* Copy This Password *

* Type Or Paste Password Here *

41,085 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>