The longest common subsequence (LCS) of two strings is the longest sequence of characters that appears in both in the same order (not necessarily next to each other); it is found by dynamic programming in \(O(mn)\) time.
Subsequence vs substring. For "ABCBDAB", "BCBA" is a subsequence (characters in order, gaps allowed); a substring must be contiguous.
Recurrence. For strings \(X = x_1\dots x_m\) and \(Y = y_1\dots y_n\), let \(c[i][j]\) be the LCS length of the first \(i\) characters of \(X\) and first \(j\) of \(Y\):
- \(c[i][j] = 0\) if \(i = 0\) or \(j = 0\)
- \(c[i][j] = c[i-1][j-1] + 1\) if \(x_i = y_j\)
- \(c[i][j] = \max(c[i-1][j],\ c[i][j-1])\) if \(x_i \ne y_j\)
Along with \(c\), keep a direction table (diagonal ↖, up ↑, left ←) to trace back the actual subsequence.
Steps.
- Make an \((m+1)\times(n+1)\) table; fill row 0 and column 0 with 0.
- Fill the table row by row using the recurrence.
- \(c[m][n]\) is the LCS length.
- Start from \(c[m][n]\) and follow the arrows back; every diagonal move gives one character of the LCS.
Example. \(X\) = ABCBDAB, \(Y\) = BDCABA. The table gives \(c[7][6] = 4\), and one LCS is BCBA (others of length 4, such as BDAB, also exist).
Why DP works. LCS has optimal substructure (the LCS of the full strings is built from the LCS of prefixes) and overlapping subproblems, so storing results avoids the exponential cost of checking all \(2^m\) subsequences.
Complexity. Time \(O(mn)\), space \(O(mn)\). Used in the diff utility, DNA sequence comparison and version control.