Hirschberg Algorithm

Purpose: Compute an optimal alignment (LCS or edit distance with the actual traceback) of two strings in $O(nm)$ time but only $O(\min (n,m))$ space — instead of the $O(nm)$ table a naive traceback needs.

The Problem It Solves

The standard $O(nm)$ DP for LCS or edit distance can be run with two rolling rows, giving the length in $O(m)$ space. But reconstructing the alignment needs the whole table. For $n=m=10^5$ that is $10^{10}$ cells — impossible. Hirschberg gets the alignment anyway.

Algorithm

Divide and conquer on the first string:

1. If $|A|\le 1$ or $|B|\le 1$, solve directly.
2. Split $A$ at its midpoint $i=|A|/2$.
3. Compute, with rolling rows only:
   • $F[j]$ = LCS length of $A[\mathrm{0..}i)$ against $B[\mathrm{0..}j)$ — a forward pass;
   • $G[j]$ = LCS length of $A[i..n)$ against $B[j..m)$ — a backward pass.
4. Choose the split point $k=\arg {\max }_j(F[j]+G[j])$. This is the column where the optimal alignment crosses the midpoint row.
5. Recurse on $(A[\mathrm{0..}i),B[\mathrm{0..}k))$ and $(A[i..n),B[k..m))$, concatenating the results.

Code

vector<int> lcsRow(const string& a, const string& b) {   // last DP row, O(|b|) space
    vector<int> prev(b.size() + 1, 0), cur(b.size() + 1, 0);
    for (size_t i = 1; i <= a.size(); i++) {
        for (size_t j = 1; j <= b.size(); j++)
            cur[j] = (a[i-1] == b[j-1]) ? prev[j-1] + 1 : max(prev[j], cur[j-1]);
        swap(prev, cur);
    }
    return prev;
}
 
string hirschberg(const string& a, const string& b) {
    if (a.empty() || b.empty()) return "";
    if (a.size() == 1) return b.find(a[0]) != string::npos ? a : "";
 
    size_t i = a.size() / 2;
    string ar(a.begin() + i, a.end()), br(b.rbegin(), b.rend());
    reverse(ar.begin(), ar.end());
 
    vector<int> F = lcsRow(a.substr(0, i), b);
    vector<int> G = lcsRow(ar, br);
 
    size_t best = 0; int bestVal = -1;
    for (size_t j = 0; j <= b.size(); j++) {
        int v = F[j] + G[b.size() - j];
        if (v > bestVal) { bestVal = v; best = j; }
    }
    return hirschberg(a.substr(0, i), b.substr(0, best))
         + hirschberg(a.substr(i),    b.substr(best));
}

Paradigm

Divide and conquer over a DP table. The same shape as D&C DP, but here the goal is memory rather than time.

Complexity

$T(n,m)=T(n/2,k)+T(n/2,m-k)+O(nm)\Rightarrow T(n,m)=O(nm),$

because the work halves geometrically: $nm+nm/2+nm/4+\cdots \le 2nm$. So Hirschberg costs at most twice the plain DP in time, and asymptotically nothing extra.

• Time: $O(nm)$ (constant factor ~2)
• Space: $O(\min (n,m))$ plus $O(\log n)$ recursion

Correctness

The optimal alignment path in the DP grid must cross row $i$ somewhere — say at column $k$. Splitting the alignment there gives an optimal alignment of $A[\mathrm{0..}i)$ with $B[\mathrm{0..}k)$ and an optimal alignment of the suffixes (otherwise you could improve the whole). Hence ${\max }_j(F[j]+G[j])$ is exactly the optimal value, and any maximiser is a valid crossing point. ∎

Variants / Use Cases

• Needleman-Wunsch with linear space — the original bioinformatics motivation; aligning two genomes is impossible otherwise
• Smith-Waterman (local alignment) — the same trick applies
• Edit distance with traceback on very long strings
• Space optimization — the general topic; Hirschberg is its most elegant instance
• Knuth / D&C DP — the same divide-and-conquer skeleton used for speed instead