1 Longest Common Subsequence

Given two strings X = hx1 , x2 , . . . , xm i and Y = hy1 , y2 , . . . , yn i of length m and n respectively. xi can also be represented as
X[i] where 1 ≤ i ≤ m. Similarly, yj can also be represented as Y [j] where 1 ≤ j ≤ n.
Algorithm 1 is used to find the length of longest common subsequence of X and Y considering initial m characters of X and
initial n characters of Y . Our aim is to find the length of the longest common subsequence of X and Y (considering entire length
of X and Y ). So the initial call to Algorithm 1 is LCS(X, Y, m, n).

Algorithm 1 LCS(X, Y, m, n)
1: if m = 0 k n = 0 then . Base condition
2: return 0
3: end if
4: if X[m] = Y [n] then . mth character of X is same as nth character of Y
5: return 1 + LCS(X, Y, m − 1, n − 1) . Find the longest common subsequence of hx1 , x2 , . . . , xm−1 i and hy1 , y2 , . . . , yn−1 i
6: else . mth character of X is different from nth character of Y
7: return max (LCS(X, Y, m − 1, n), LCS(X, Y, m, n − 1)) . Find the longest common subsequence of hx1 , x2 , . . . , xm−1 i
and hy1 , y2 , . . . , yn i. Also find the longest common subsequence of hx1 , x2 , . . . , xm i and hy1 , y2 , . . . , yn−1 i. After this
consider the maximum one
8: end if

T (m, n) = T (m − 1, n) + T (m, n − 1) + O(1) (1)

1. Maximum height/depth of the tree for the recurrence = m + n − 1 so

T (m, n) ≤ 1 + 2 + 22 + 23 + · · · + 2m+n−1
 

= 2m+n − 1 (2)

2. Minimum depth of the tree for the recurrence = n so

T (m, n) ≥ 1 + 2 + 22 + 23 + · · · + 2n
 

= 2n+1 − 1 (3)
 Algorithm 2 is used to find the length of the longest common subsequence of X and Y considering initial m characters of X
and initial n characters of Y . Our aim is to find the length of the longest common subsequence of X and Y (considering entire
length of X and Y ). So the initial call to Algorithm 2 is LCS(X, Y, m, n). In this Algorithm, we are using a 2D-array (say T)
of size (m + 1) × (n + 1) and initialize it with −1 (any negative value) because the length of the longest common subsequence
cannot be negative. This array is used to avoid repetition of the same work.

Algorithm 2 LCS-Store(X, Y, m, n)
1: if m = 0 k n = 0 then . Base condition
2: return 0
3: end if
4: if T[m][n] 6= −1 then . Longest common subsequence of hx1 , x2 , . . . , xm i and hy1 , y2 , . . . , yn i is already computed
5: return T[m][n]
6: end if
7: if X[m] = Y [n] then . mth character of X is same as nth character of Y
8: if T[m − 1][n − 1] 6= −1 then . Longest common subsequence of hx1 , x2 , . . . , xm−1 i and hy1 , y2 , . . . , yn−1 i
is already computed
9: return T[m − 1][n − 1]
10: else
11: T[m][n] ← 1 + LCS-Store(X, Y, m − 1, n − 1) . Find the longest common subsequence of hx1 , x2 , . . . , xm−1 i
and hy1 , y2 , . . . , yn−1 i
12: return T[m][n]
13: end if
14: else . mth character of X is different from nth character of Y
15: if T[m − 1][n] 6= −1 then . Longest common subsequence of hx1 , x2 , . . . , xm−1 i and hy1 , y2 , . . . , yn i
is already computed
16: β ← T[m − 1][n]
17: else
18: β ← LCS-Store(X, Y, m − 1, n) . Find the longest common subsequence of hx1 , x2 , . . . , xm−1 i and hy1 , y2 , . . . , yn i
19: end if
20: if T[m][n − 1] 6= −1 then . Longest common subsequence of hx1 , x2 , . . . , xm i and hy1 , y2 , . . . , yn−1 i
is already computed
21: γ ← T[m][n − 1]
22: else
23: γ ← LCS-Store(X, Y, m, n − 1) . Find the longest common subsequence of hx1 , x2 , . . . , xm i and hy1 , y2 , . . . , yn−1 i
24: end if
25: T[m][n] ← max (β, γ) . Find the maximum of β and γ
26: return T[m][n]
27: end if

1. Top-down approach
2. Number of distinct sub-problems = (m + 1) × (n + 1)

3. Each sub-problem is solved exactly once.