## 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