Hunt–Szymanski Algorithm¶

A longest-common-subsequence algorithm that orders equal-symbol index pairs and reduces LCS computation to thresholded increasing-subsequence updates with match-sensitive cost.

Version: v3 · 2026-09-19 · History
Domain-specific #: 2024
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: String Algorithms → Computer Science & Software Engineering

Core Idea¶

The Hunt–Szymanski algorithm computes a longest common subsequence (LCS) of two sequences by avoiding most cells of the classical \(m\times n\) dynamic-programming table. It focuses on the set of matching index pairs

\[ P=\{(i,j)\mid A_i=B_j\} \]

and exploits their partial order. A common subsequence corresponds to a chain

\[ (i_1,j_1)<\cdots<(i_k,j_k), \qquad i_1<\cdots<i_k,\quad j_1<\cdots<j_k, \]

whose paired symbols agree.

Preprocess sequence \(B\) into a list of occurrence positions for each symbol, stored in decreasing order. Sweep \(A\) from left to right. For every \(B\)-position \(j\) matching the current \(A_i\), process \(j\) in decreasing order and update a threshold array \(T\), where \(T[k]\) is the smallest second-sequence position known to end a common subsequence of length \(k\).

How would you explain it like I'm…

Only Look at Matches

Imagine two long lines of colored beads, and you want the longest pattern you can find in both, in the same order, even if you skip some beads. Instead of checking every bead against every other bead, you only look at the spots where colors match. That's much quicker when matches are rare. That's the Hunt–Szymanski Algorithm.

Matches-Only Sequence Finder

The Hunt–Szymanski Algorithm finds the longest common subsequence of two lists: the longest set of items that appear in the same order in both, possibly with gaps. The usual method fills in a big grid comparing every item of one list with every item of the other. This algorithm only pays attention to the places where items actually match. It goes through the first list, and for each matching spot in the second list it updates a small table of the best results so far. When there are few matches, this is much faster. When almost everything matches, it isn't.

Match-Sensitive LCS Algorithm

The Hunt–Szymanski Algorithm computes a longest common subsequence (LCS) of two sequences A and B without filling in the whole m×n dynamic-programming table. It works only with the matching pairs (i, j) where A_i = B_j. A common subsequence is a chain of such pairs that increase in both i and j. First, for each symbol it lists where that symbol occurs in B, in decreasing order. Then it scans A from left to right and keeps a threshold array T. T[k] is the smallest position in B known to end a common subsequence of length k. For each matching j, binary search finds the largest k with T[k] < j, and j may improve T[k+1]. Handling j in decreasing order stops two matches from the same A_i from being counted together. It's fast when matches are rare but can be as slow as the grid when symbols repeat everywhere.

The Hunt–Szymanski Algorithm solves the longest common subsequence (LCS) problem by working over the match set P = {(i, j) : A_i = B_j} rather than the full m×n DP table. Common subsequences correspond to chains in P under the strict product order, where both i and j increase. Preprocessing stores, for each symbol, its occurrence positions in B in decreasing order. The algorithm sweeps A left to right. For each j matching A_i, taken in decreasing order, it updates a threshold array T, where T[k] is the smallest B-position known to end a common subsequence of length k. Binary search locates the largest k with T[k] < j, after which j may replace T[k+1]. Processing in descending order guarantees that matches sharing the same i cannot be chained to each other. With r = |P|, a standard bound is O((r + n) log n) under suitable preprocessing conventions. Recovering the actual subsequence requires storing predecessor links. The method is match-sensitive rather than universally subquadratic: when symbols repeat heavily, r can be Θ(mn).

Scope of Application¶

The algorithm is suited to sequence pairs where exact symbol matches are relatively sparse: source files whose lines are mostly distinct, token streams, version histories, some biological sequences, and structured records with large alphabets.

Its output can support a shortest insertion/deletion edit script, because an LCS identifies symbols preserved in order. Replacement cost conventions and move detection are additional layers.

Implementations choose whether symbols are characters, lines, tokens, hashes, or domain objects with an equality predicate. Hashing can accelerate candidate lookup, but collisions must be verified by actual equality if exactness matters.

Clarity¶

The lists for \(B\)-positions must be processed in decreasing order for each fixed \(i\). Suppose \(A_i\) matches \(B_2\) and \(B_5\). Processing 2 before 5 could let the threshold update for 2 support the update for 5, falsely using \(A_i\) twice. Processing 5 then 2 prevents this.

Manages Complexity¶

The full LCS table considers every prefix pair, most of which may contain no equal terminal symbols. Hunt–Szymanski compresses the search to equality events and a frontier of nondominated endpoints.

The threshold array has at most \(\min(m,n)+1\) logical entries. Binary search replaces a scan through candidate subsequence lengths. Precomputed occurrence lists avoid searching all of \(B\) for each \(A_i\).

Abstract Reasoning¶

Initialize \(T[0]=0\) and \(T[k]=+\infty\) for \(k>0\), using one-based positions. For each matching position \(j\), find

\[ k=\max\{\ell\mid T[\ell]<j\}. \]

Then set

\[ T[k+1]\leftarrow\min(T[k+1],j). \]

Inductively, \(T[k]\) is the smallest ending position in \(B\) of any common subsequence of length \(k\) found after the processed prefix of \(A\).

Knowledge Transfer¶

The mechanism transfers literally from character strings to line, token, event, and biological-symbol sequences. The equality index changes, but match pairs, strict coordinate order, threshold dominance, and backtracking remain.

File comparison was an important motivating habitat. The Hunt–McIlroy diff work established candidate-matching ideas; Hunt and Szymanski supplied a rigorously analyzed match-sensitive LCS algorithm. Modern tools may combine its core with heuristics for unique anchors, patience, bounded memory, or readable hunks.

Relationships to Other Abstractions¶

Current abstraction Hunt–Szymanski Algorithm Domain-specific

Parents (1) — outgoing typed relations

Hunt–Szymanski Algorithm is a kind of Algorithm Prime

prime:algorithm is the broader abstraction this entry instantiates.

Hierarchy path (1) — routes to 1 parentless root

Hunt–Szymanski Algorithm → is a kind of Algorithm → presupposes, conditional Function (Mapping)

Neighborhood in Abstraction Space¶

Hunt–Szymanski Algorithm sits in a sparse region of the domain-specific corpus (84^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25