Longest Common Sub-sequence(LCS)

Given two strings: string S of length n, and string T of length m. The longest common sub-sequence is the longest sequence of characters that appear left-to-right (but not necessarily in a contiguous block) in both strings.

Dynamic Programming Solution:

LCS[i,j] is the length of the LCS of S[1..i] with T[1..j]. 

If S[i] != T[j] then, LCS[i,j] = max(LCS[i−1,j],LCS[i,j−1])

If S[i] = T[j] then, LCS[i,j] = 1 + LCS[i−1,j−1]

Example:

Implementation:

int LCS(std::string S, std::string T)

{

int m = S.size();

int n = T.size();

if(m == 0 || n == 0)

return 0;

int **LCS = new int*[m + 1];

for(int i = 0; i <= m; ++i)

{

LCS[i] = new int[n + 1];

LCS[i][0] = 0;

}

for(int j = 0; j <= n; ++j)

LCS[0][j] = 0;

for(int i = 1; i <= m; ++i)

{

for(int j = 1; j <= n; ++j)

{

if(S[i-1] != T[j-1])

LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);

else

LCS[i][j] = 1 + LCS[i-1][j-1];

}

}

return LCS[m][n];

}

Time Complexity: O(mn)