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)

## No comments:

## Post a Comment