BDFH is a subsequence of ABCDEFGH. Given two lists, what’s the longest common subsequence?

optimal substructure

We consider sub problems’ of finding LCS of prefixes \(C[i,j]\). Casework:

C[i,j] = …

• for A[i] = B[j], then C[i,j] = C[i-1, j-1] + 1
• for A[i] != B[j] = max(C[i,j-1], C[i-1,j])
• if i=0 or j=0, then 0

Filling this table is \(O\qty(nm)\), and backtracing takes \(O\qty(n+m)\).