Longest Common Subsequence

The longest common subsequence finds the longest ordering of characters shared by two strings, solved with a two-dimensional DP table.

Shared order, not contiguity

A subsequence keeps characters in order but need not keep them adjacent. The longest common subsequence (LCS) of two strings is the longest sequence of characters appearing in both in the same relative order. For ABCBDAB and BDCAB, one LCS is BCAB of length four. LCS measures similarity while tolerating insertions and deletions.

The recurrence

Let L[i][j] be the LCS length of the first i characters of one string and the first j of the other. If the current characters match, L[i][j] = L[i-1][j-1] + 1. If they differ, L[i][j] = max(L[i-1][j], L[i][j-1]), dropping one character from either string. The base cases with an empty prefix are zero.

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

• Time: O(m*n)
• Space: O(m*n), reducible to O(min(m,n)) for the length only
• Reconstruct the actual subsequence by tracing back through the table
• A textbook dynamic-programming problem

Subsequence versus substring

It is worth stressing the difference: a subsequence may skip characters, while a substring must be contiguous. The longest common substring is a different, easier problem solved by a related table that resets to zero on a mismatch. LCS is the harder and more useful measure when comparing texts that have had lines inserted or removed.

Where it is used

LCS underlies the diff tools that compare file versions, version-control merge algorithms, and DNA and protein sequence alignment in bioinformatics. It is closely related to edit distance: both measure how far apart two sequences are, and both are solved by filling a two-dimensional table with a similar recurrence. In fact the edit distance using only insertions and deletions equals m plus n minus twice the LCS length.