The longest common subsequence (LCS) of two sequences is the longest sequence of letters that appears in both in the same order. It underlies diff tools and DNA comparison.

Subsequence versus substring

  • A substring is made of consecutive letters: "BCB" is a substring of "ABCBDAB".
  • A subsequence keeps the order but may skip letters: "BCBA" is a subsequence of "ABCBDAB".

For X = "ABCBDAB" and Y = "BDCABA" the LCS has length 4 (for example "BCBA").

State and transition

  • State: dp[i][j] is the LCS length of the first i letters of X and the first j letters of Y.
  • Base: dp[0][j] = dp[i][0] = 0.
  • Match (X[i-1] == Y[j-1]): dp[i][j] = dp[i-1][j-1] + 1.
  • Mismatch: dp[i][j] = max(dp[i-1][j], dp[i][j-1]), drop one letter.
  • Answer: dp[n][m].
LCS table for "ABCBDAB" and "BDCABA" with the trace-back path
LCS table for "ABCBDAB" and "BDCABA" with the trace-back path
python
def lcs_table(x, y):
    n, m = len(x), len(y)
    # dp[i][j]: LCS length of x[:i] and y[:j]
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1              # match: extend
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])   # drop one letter
    return dp