Longest Common Subsequence

(Dynamic Programming)

Design and Analysis of Algorithm (CS1501)

Satpal Singh Kushwaha (Assistant Professor

(Senior Scale))
Manipal University Jaipur
 Dynamic programming
• It is used, when the solution can be recursively
described in terms of solutions to subproblems
(optimal substructure)
• Algorithm finds solutions to subproblems and
stores them in memory for later use
• More efficient than “brute-force methods”, which
solve the same subproblems over and over again

2
 Longest Common Subsequence
(LCS)

Application: comparison of two DNA strings

Ex: X= {A B C B D A B }, Y= {B D C A B A}
Longest Common Subsequence:
X= AB C BDAB
Y= BDCAB A
Brute force algorithm would compare each
subsequence of X with the symbols in Y

03/01/2025 3
 Longest Common Subsequence
Input: X = < x 1 , x 2, …, x m>
Y = < y1 , y2 , …, y n >

Output: a longest common subsequence (LCS) of X and Y.

Example a) X = abcbdab Y = bdcaba

LCS1 = bcba LCS 2 = bdab
b) X = enquiring Y = sequipedalian
LCS = equiin

c) X = empty bottle Y = nematode knowledge

LCS = emt ole
 LCS Algorithm
• if |X| = m, |Y| = n, then there are 2m subsequences of
x; we must compare each with Y (n comparisons)
• So the running time of the brute-force algorithm is
O(n 2m)
• Notice that the LCS problem has optimal
substructure: solutions of subproblems are parts of
the final solution.
• Subproblems: “find LCS of pairs of prefixes of X and
Y”

03/01/2025 5
 LCS Algorithm
• First we’ll find the length of LCS. Later we’ll modify
the algorithm to find LCS itself.
• Define Xi, Yj to be the prefixes of X and Y of length i
and j respectively
• Define c[i,j] to be the length of LCS of Xi and Yj
• Then the length of LCS of X and Y will be c[m,n]

c[i  1, j  1]  1 if x[i ]  y[ j ],
c[i, j ] 
 max(c[i, j  1], c[i  1, j ]) otherwise
03/01/2025 6
 LCS recursive solution
c[i  1, j  1]  1 if x[i ]  y[ j ],
c[i, j ] 
 max(c[i, j  1], c[i  1, j ]) otherwise
• We start with i = j = 0 (empty substrings of x and y)

• Since X0 and Y0 are empty strings, their LCS is

always empty (i.e. c[0,0] = 0)
• LCS of empty string and any other string is empty, so
for every i and j: c[0, j] = c[i,0] = 0

03/01/2025 7
 LCS recursive solution
c[i  1, j  1]  1 if x[i ]  y[ j ],
c[i, j ] 
 max(c[i, j  1], c[i  1, j ]) otherwise
• When we calculate c[i,j], we consider two cases:
• First case: x[i]=y[j]: one more symbol in strings X
and Y matches, so the length of LCS Xi and Yj equals
to the length of LCS of smaller strings X i-1 and Yi-1 ,
plus 1

03/01/2025 8
 LCS recursive solution
c[i  1, j  1]  1 if x[i ]  y[ j ],
c[i, j ] 
 max(c[i, j  1], c[i  1, j ]) otherwise

• Second case: x[i] != y[j]

• As symbols don’t match, our solution is not improved,
and the length of LCS(Xi , Yj) is the same as before i.e.
maximum of LCS(Xi, Yj-1) and LCS(Xi-1,Yj)

03/01/2025 9
 LCS recursive solution

03/01/2025 10
A Recursive Formula
X = < x 1, x 2, …, xm >, Y = < y1 , y 2, …, yn >

c[i, j] = length of an LCS of < x , …, x > and < y , …, y > .

1 i 1 j

Then c[m,n] = length of an LCS of X and Y.

Computing the Length of the LCS
0 if i = 0 or j
=0
c[i, j] = c[i-1, j-1] + 1 if xi =
yj
0 1 2 n
max(c[i,
yj: y1 j-1],
y2 c[i-1, j])yn if xi  yj
0 xi 0 0 0 0 0 0
1 x1 0 first
2 x2 0 second
i
0
0
m xm 0
j
12
Additional Information
0 if A matrix b[i, j]:
i,j = 0
• For a subproblem [i, j] it
c[i, j] = c[i-1, j-1] + 1 if xi = tells us what choice was
yj
made to obtain the
0 max(c[i,
1 2 j-1],
3 c[i-1,nj])
b & c: y if Ax  Cy D F optimal value
j: i j

0 xi 0 0 0 0 0 0 • If xi = yj
1 A 0 b[i, j] = “ ”
2 B 0 c[i-1,j-1] • Else, if
c[i-1,j]
i c[i - 1, j] ≥ c[i, j-1]
3 C 0 c[i,j-1]
0 b[i, j] = “  ”
0 else
m D
b[i, j] = “  ”
j
13
LCS-LENGTH(X, Y, m, n)
The length of the LCS if one of the sequences
1. for i ← 1 to m
is empty is zero
2. do c[i, 0] ← 0
3. for j ← 0 to n
4. do c[0, j] ← 0
5. for i ← 1 to m
6. do for j ← 1 to n
7. do if xi = yj
Case 1: xi = yj
8. then c[i, j] ← c[i - 1, j - 1] + 1
9. b[i, j ] ← “ ”
10. else if c[i - 1, j] ≥ c[i, j - 1]
11. then c[i, j] ← c[i - 1, j]
12. b[i, j] ← “↑” Case 2: xi  yj
13. else c[i, j] ← c[i, j - 1]
14. b[i, j] ← “←”
15. return c and b
Running time: (mn)
14
Example 0 if i = 0 or
X = A, B, C, B, D, A, B j=0
Y = B, D, C, A, B, A c[i, j] = c[i-1, j-1] + 1 if xi = yj
0 1 2
max(c[i, 3
j-1], 4
c[i-1,5j]) if6 xi  yj
If xi = yj yj B D C A B A
0 xi
b[i, j] = “ ” 0 0 0 0 0 0 0
1 A   
Else if c[i - 0 0 0 0 1 1 1
2 B 
1, j] ≥ c[i, j-1] 0 1 1 1 1 2 2
   
b[i, j] = “  ”3 C 0 1 1 2 2 2 2
  
else 4 B 0 1 1 2 2 3 3
b[i, j] = “  5” D 0

1 2

2

2

3

3
   
6 A 0 1 2 2 3 3 4
   
7 B 0 1 2 2 3 4 4
15
PRINT-LCS(b, X, i, j)
1. if i = 0 or j = 0 Running time: (m + n)
2. then return
3. if b[i, j] = “ ”
4. then PRINT-LCS(b, X, i - 1, j - 1)
5. print xi
6. elseif b[i, j] = “↑”
7. then PRINT-LCS(b, X, i - 1, j)
8. else PRINT-LCS(b, X, i, j - 1)

Initial call: PRINT-LCS(b, X, length[X], length[Y])

17
Constructing a LCS
• Start at b[m, n] and follow the arrows
• When we encounter a “ “ in b[i, j]  xi = yj is an element of
the LCS
0 1 2 3 4 5 6
yj B D C A B A
0 xi 0 0 0 0 0 0 0
1 A   
0 0 0 0 1 1 1
2 B 
0 1 1 1 1 2 2
3 C    
0 1 1 2 2 2 2
  
4 B 0 1 1 2 2 3 3
5 D     
0 1 2 2 2 3 3
   
6 A 0 1 2 2 3 3 4
   
7 B 0 1 2 2 3 4 4
18