Longest Common Subsequence

A subsequence preserves order but need not be contiguous. Given sequences $X$ and $Y$, the LCS problem asks for a maximum-length sequence that is a subsequence of both.

MIT’s LCS lecture presents LCS as a dynamic program over sequence states.

Let $dp[i][j]$ be the LCS length of prefixes $X[:i]$ and $Y[:j]$:

$$dp[i][j] = \begin{cases} dp[i-1][j-1]+1, & X[i-1]=Y[j-1],\\ \max(dp[i-1][j],dp[i][j-1]), & \text{otherwise}. \end{cases}$$

Empty-prefix rows and columns are zero.

def lcs_length(left: str, right: str) -> int:
    previous = [0] * (len(right) + 1)
    for left_item in left:
        current = [0]
        for j, right_item in enumerate(right, start=1):
            if left_item == right_item:
                current.append(previous[j - 1] + 1)
            else:
                current.append(max(previous[j], current[-1]))
        previous = current
    return previous[-1]

Cost and output

• Full table: $O(mn)$ time and $O(mn)$ space.
• Length only: $O(mn)$ time and $O(\min(m,n))$ space after choosing the shorter sequence as the row width.
• Reconstructing an LCS requires retained choices, a full table, or a more specialized divide-and-conquer reconstruction.

The longest common substring is a different problem because matching symbols must be contiguous.

Deriving and reading the table

If the last symbols differ, a common subsequence cannot use both as its final match: discard at least one, hence the maximum of the two shorter-prefix states. If they match, an optimum can use that final match; appending it to an optimum for the two shorter prefixes gives the diagonal transition. All dependencies have smaller prefix lengths, establishing induction and termination.

For left="ABC", right="AC", the rows (including the empty prefix) are [0,0,0], [0,1,1], [0,1,1], [0,1,2]. Thus the length is 2, and AC is a witness. Either empty string gives length zero. To reconstruct from a full table, start at (m,n): on equal symbols record the symbol and move diagonally; otherwise move to a neighbor with the same optimal value. Reverse the recorded symbols. Ties may yield different, equally long subsequences.

The code above uses O(len(right)) space as written. Swap the inputs first when right is longer to realize the O(min(m,n)) bound.

assert lcs_length("ABC", "AC") == 2
assert lcs_length("", "AC") == 0

Enter ABC and AC in the USF LCS workbench and choose the table method. At each cell, distinguish an equal-character diagonal step from a maximum over shorter prefixes. Then change one character and predict which part of the table must change.

Source

• MIT OpenCourseWare: Dynamic Programming II

My reading · Opened notes are remembered in this browser.