AlgoVerse

Longest common subsequence (LCS)

Find the longest subsequence that appears in both strings (in the same order, not necessarily side by side) with a dynamic-programming table.

A subsequence comes from deleting some characters (not necessarily side by side). We want the longest subsequence common to two strings; for example to compare files (diff) or DNA.

Read the full explanation ↓
Input:
X="ABCBDAB" · Y="BDCABA"PDF export

X = ABCBDAB and Y = BDCABA; the LCS has length 4, and one answer is BCBA.

  1. def lcs(X, Y):
  2. m, n = len(X), len(Y)
  3. # c[i][j] = the LCS length of X[:i] and Y[:j]; row 0 and column 0 are the empty prefixes.
  4. c = [[0] * (n + 1) for _ in range(m + 1)]
  5. for i in range(1, m + 1):
  6. for j in range(1, n + 1):
  7. if X[i - 1] == Y[j - 1]:
  8. c[i][j] = c[i - 1][j - 1] + 1
  9. elif c[i - 1][j] >= c[i][j - 1]:
  10. c[i][j] = c[i - 1][j]
  11. else:
  12. c[i][j] = c[i][j - 1]
  13. # Walk back from the corner to read one longest common subsequence.
  14. out = []
  15. i, j = m, n
  16. while i > 0 and j > 0:
  17. if X[i - 1] == Y[j - 1]:
  18. out.append(X[i - 1])
  19. i, j = i - 1, j - 1
  20. elif c[i - 1][j] >= c[i][j - 1]:
  21. i = i - 1
  22. else:
  23. j = j - 1
  24. return "".join(reversed(out))

Invariant: c[i][j] is the LCS length of the prefixes X[:i] and Y[:j], and depends only on the cells above, to the left and diagonally.

Start

0123456
ABCBDAB
BDCABA
out—

The table is still empty.

Local variables

X'ABCBDAB'
Y'BDCABA'

Orange = changed in this step

Call stack

  1. lcs()line 1
Step 1 of 210
Black = take · Orange = key stepfrom_above: 0/24 · diagonal: 0/12 · from_left: 0/6 · take: 0/4
    Explanation

    The idea

    A subsequence comes from deleting some characters (not necessarily side by side). We want the longest subsequence common to two strings; for example to compare files (diff) or DNA.

    Dynamic programming

    c[i][j] is the LCS length of X[:i] and Y[:j]:

    • if the last characters are equal, that character is in the LCS: c[i−1][j−1] + 1;
    • otherwise one of the two last characters is not in it: max(c[i−1][j], c[i][j−1]).

    The table fills row by row, and walking back from the bottom-right corner reads off the LCS itself.

    Cost

    (m + 1)(n + 1) cells at O(1) each: O(m·n); against the 2ᵐ possible subsequences of the brute-force method.

    What to watch in the trace

    • The table c (row 0 and column 0 are the empty prefixes), and out, which fills from the end during the walk back.