Instead of finding the longest common

subsequence, let us try to determine the

length of the LCS.

􀂄 Then tracking back to find the LCS.

􀂄 Consider a1a2…am and b1b2…bn.

􀂄 Case 1: am=bn. The LCS must contain am,

we have to find the LCS of a1a2…am-1 and

b1b2…bn-1.

􀂄 Case 2: am≠bn. Wehave to find the LCS of

a1a2…am-1 and b1b2…bn, and a1a2…am and

b b b

b1b2…bn-1



Let A = a1 a2 … am and B = b1 b2 … bn

􀂄 Let Li j denote the length of the longest i,g g

common subsequence of a1 a2 … ai and b1 b2

… bj.

􀂄 Li,j = Li-1,j-1 + 1 if ai=bj

max{ L L } a≠b i-1,j, i,j-1 if ai≠j

L0,0 = L0,j = Li,0 = 0 for 1≤i≤m, 1≤j≤n.-Instead of finding the longest commonsubsequence, let us try to determine thelength of the LCS .