Beginning Java Data Structures and Algorithms

Longest Common Subsequence

Now, let's look at a different problem which is solvable by a dynamic programming algorithm. The problem we're now interested in is the longest common subsequence problem.

The difference between a subsequence and a substring is that a substring is a consecutive subsequence. For example, [a, d, f] is a subsequence of [a, b, c, d, e, f], but not a substring. [b, c, d] is a substring and a subsequence of [a, b, c, d, e, f].

We're interested in finding similarities between two given sequences by computing the Longest Common Subsequence (LCS) between them. A common subsequence, S₃, of two given sequences, S₁ and S₂, is a sequence whose elements appear in both S and S₂ in the same order, but not necessarily consecutively. ...