Longest Common Subsequence

The longest sequence appearing (not necessarily contiguously) in both strings.

The recurrence

$$dp[i][j]=\{\begin{array}{ll}0& i=0\text{ or }j=0\\ dp[i-1][j-1]+1& a_i=b_j\\ \max (dp[i-1][j],dp[i][j-1])& \text{otherwise}\end{array}$$

int lcs(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = (a[i-1] == b[j-1]) ? dp[i-1][j-1] + 1
                                          : max(dp[i-1][j], dp[i][j-1]);
    return dp[n][m];
}

$O(nm)$ time and space; $O(\min (n,m))$ space with a rolling array.

Reconstructing the subsequence

string reconstruct(const string& a, const string& b, vector<vector<int>>& dp) {
    string res;
    int i = a.size(), j = b.size();
    while (i > 0 && j > 0) {
        if (a[i-1] == b[j-1]) { res += a[i-1]; i--; j--; }
        else if (dp[i-1][j] >= dp[i][j-1]) i--;
        else j--;
    }
    reverse(res.begin(), res.end());
    return res;
}

Needs the full table. With only two rows, use Hirschberg’s algorithm — $O(nm)$ time, $O(\min (n,m))$ space, and it still produces the actual subsequence.

Beating $O(nm)$

Situation	Method	Time
Both strings are permutations	map to indices, run LIS	$O(n\log n)$
One string has few distinct characters	Hunt-Szymanski	$O((r+n)\log n)$, $r$ = matching pairs
Small alphabet, need raw speed	bit-parallel (Crochemore-Iliopoulos-Pinzon)	$O(nm/64)$
The answer is known to be short/long	banded DP around the diagonal	$O(nk)$

The permutation trick

If $a$ and $b$ are permutations of the same multiset with distinct elements, replace each element of $b$ by its position in $a$. A common subsequence of the two is exactly an increasing subsequence of that new array. $O(n\log n)$ instead of $O(n^2)$.

Lower bound: no $O(n^{2-\epsilon })$ algorithm exists for general LCS unless the Strong Exponential Time Hypothesis fails. The quadratic barrier is real.

The related family

Problem	Difference
Longest common substring (contiguous)	dp[i][j] = dp[i-1][j-1]+1 on match, 0 otherwise; or use a suffix automaton for $O(n)$
Edit distance	minimisation with insert/delete/replace
Shortest common supersequence	$n+m-\mathrm{LCS}$
Longest palindromic subsequence	LCS of $s$ and $\mathrm{reverse}(s)$
Minimum insertions to make a palindrome	$n-\mathrm{LPS}$
LCS of $k$ strings	$O(n^k)$ — NP-hard in $k$
Longest common increasing subsequence	$O(nm)$ with a running maximum
Diff (Myers’ algorithm)	LCS with an $O((n+m)d)$ algorithm where $d$ is the edit distance — what git diff uses

The palindromic subsequence reduction is the most reused: LPS$(s)$ = LCS$(s,\mathrm{reverse}(s))$, so any LCS code solves palindrome problems for free.

Counting distinct LCS

Add a count array alongside the length array, being careful not to double-count when both dp[i-1][j] and dp[i][j-1] achieve the maximum — subtract dp[i-1][j-1]’s count by inclusion-exclusion when the characters differ and both branches tie.

See also: Edit Distance · LIS · Hirschberg