Home > Algorithms, Computer Programming, Computer Science > Finding Longest Common Subsequence !

Finding Longest Common Subsequence !

Well I will be getting some what techie. in this post , i recently tried and solved the Longest Common Subsequence problem once again , which is a really hard problem to solve(if you have not heard it before or never tried it).

Well, consider the text string S = 'i am a computer programmer' and another text string T = "a crammer" now this is contained in the string S , read the letters in capital in S, 'i Am a Computer pRogrAMMER', now this is the problem of finding any substring of T in S at any place in any form and the one which is the longest.

I solved this problem in a programming competition by generating all the subsets of strings S and T and finding the longest in subset strings of S. But the code was too complex and the complexity was 2^N for subsets and log(n) for search even the code was iterative. However thanks to Dynamic Programming that this problem can be solved in O( M * N ) worst case time complexity, where M = length of string S and N = Length of string T

the dynamic programming algorithm or pseduocode is;

int FindMaxLengthSubstring( S, T )
{
 // make a 2 D array say MaxLen of size M * N for logical thinking
 for ( int i = 0; i < Len(S); i++)
 {
  for (int j = 0; j < Len(T); j++)
  {
   if (S[i] == L[j] )
   {
    if( i==0 || j ==0)
    {
     MaxLen [i][j] = maximum( in 0th row or 0th column of MaxLen) + 1;
     continue;
     }    
     MaxLen [i][j] = 1 + MaxLen[ i – 1 ][ j – 1 ];
   }
   else
    MaxLen[i][j] = maximum( MaxLen[ i – 1][ j], MaxLen [ i ][  j – 1 ]);   
  }  
 }
 return MaxLen[Len(S) – 1][Len(T) – 1]; 
}

maximum is the simple function that find maximum of 2 numbers. Remember this function only returns the length of longest common subsequence only. Not the original such substring. We can find such substring in MaxLen array by back tracking and moving upwards. I will explain the logic for this solution some time soon.

I, Haroon

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: