An optimal length and an actual sequence are different outputs
For ABC and AC, the sequence AC appears in both inputs if we
may skip symbols. It need not occupy adjacent positions in ABC.
The task is to find a longest common subsequence, not a longest common
contiguous substring. The distinction determines the allowed choices
in the recurrence.
A second distinction appears when optimizing memory. A single row can compute an optimal length, but it does not preserve the whole traceback that a full table provides. We will first prove the table method, then derive a reconstruction that deliberately recomputes selected rows.
Prefixes make the state precise
Definition 8.1.1
(Subsequence and prefix LCS length)
Let and be finite sequences of symbols with a well-defined equality test. A subsequence is selected at strictly increasing indices; positions need not be consecutive. An alignment of a common subsequence pairs equal symbols at increasing indices in both inputs.
Define as the maximum common-subsequence length of prefixes and . Empty prefixes have length 0, so .
Assume symbol equality and each table-cell operation have constant cost. The table indices count prefix lengths; they are not indices of a possibly nonexistent last symbol of an empty prefix.
Theorem 8.1.2
(The prefix recurrence)
For ,
Proof
(Prove that every candidate fits, and that a bound is attainable)
Suppose . Append this symbol to an optimal alignment of the two shorter prefixes, obtaining length . For the reverse bound, consider any common-subsequence alignment. If it uses either terminal index i or j, the pair containing that index must be the final pair. Deleting that pair leaves an alignment in both shorter prefixes, so the original length is at most . If it uses neither terminal index, it already fits those prefixes and obeys the same bound. Thus equality holds.
If , an alignment cannot use both terminal indices. They cannot be paired together, and pairing them separately would contradict increasing order: the pair using i must be last, as must the pair using j. Therefore at least one terminal index is unused, so every candidate is contained in one of the two prefix problems. Its length is at most their maximum. Conversely, each prefix optimum is still a common subsequence of the full prefixes, attaining that maximum.
Proof X-ray
Why only the terminal indices matter
The two directions of the proof differ in strength. The lower bound needs only that appending a matching pair after any alignment of the shorter prefixes keeps the indices increasing; the equality is used exactly there. The upper bound is the substantive half. It needs the observation that a pair using either terminal index must be the last pair, because every other pair has smaller indices on both sides. Deleting it leaves an alignment of strictly shorter prefixes.
The key move is to case on whether the terminal symbols are used, rather than on which alignment is optimal. When the same move shows that both cannot be used: the pair containing and the pair containing must each be last, hence they are one pair, which would match with .
Each case reduces to a strictly shorter prefix pair, , or , so induction on closes the argument from the empty-prefix base. If the subsequence had to be contiguous, deleting the last pair would not stay in the same family of objects, and the state and recurrence would have to change.
Fill cells in increasing i and j so all dependencies are available. This proves by induction that the computed table equals the specified optimum at every prefix. The final length is , in table storage and time; for nonempty inputs this is .
Trace a table entry back to a sequence
TRACE_LCS(X, Y, L):
i = length(X)
j = length(Y)
reversed_output = empty buffer
while i > 0 and j > 0:
if X[i-1] == Y[j-1]:
append X[i-1] to reversed_output
i = i - 1
j = j - 1
else if L[i-1,j] >= L[i,j-1]:
i = i - 1
else:
j = j - 1
return reverse(reversed_output)
Here sequence accesses are zero-based while L still uses prefix lengths. The sequence is collected backwards, hence the final reversal.
Theorem 8.1.3
(Traceback returns an optimal common subsequence)
Given the full table , TRACE_LCS returns a common subsequence of length , and it performs at most iterations.
Proof
(A length-conserving traceback invariant)
Let be the number of symbols collected so far. At the start of every iteration . This holds initially with . If , the recurrence gives , and the algorithm collects one symbol and moves diagonally. Otherwise , and the >= test moves to a predecessor attaining the maximum, so neither nor the value of changes. The loop stops when or , where , so . The collected symbols come from index pairs that decrease in both inputs, so after reversal they form a common subsequence. Each iteration decreases or .
Each step decreases i or j, so traceback takes time
once the table exists. The >= rule resolves ties by moving up;
it selects one optimum and does not enumerate every optimal sequence
or every possible alignment of the same sequence.
Concept lensGeometric
The table as a longest path in a grid
Draw the grid of prefix pairs . A step from or to has weight ; a diagonal step from to is allowed only when and has weight . Then is the largest total weight of a path from to , and each diagonal step is one matched pair. Traceback recovers an optimal path backwards. Every path to crosses any fixed row at some column , which is exactly the split into used later.
Worked example 8.1.4
(ABAB and BABA have multiple optimal answers)
Rows are prefixes of ABAB, columns prefixes of BABA:
| X prefix | Empty | B | BA | BAB | BABA |
|---|---|---|---|---|---|
| Empty | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 1 | 1 | 1 |
| AB | 0 | 1 | 1 | 2 | 2 |
| ABA | 0 | 1 | 2 | 2 | 3 |
| ABAB | 0 | 1 | 2 | 3 | 3 |
The optimum is 3. The shown up-on-tie traceback returns ABA.
Choosing the left predecessor at the final tie instead can return BAB.
Both answers have increasing matching positions in both strings; the
length proof does not imply uniqueness.
A rolling row must preserve the old diagonal
For the length alone, the previous row and the current row are enough. One array suffices if its entries are updated left to right:
LCS_ROW(X, Y):
m = length(Y)
dp = array of m + 1 zeros
for each symbol x in X:
diagonal = 0
for j from 1 through m:
old = dp[j]
if x == Y[j-1]:
dp[j] = diagonal + 1
else:
dp[j] = max(dp[j], dp[j-1])
diagonal = old
return dp
Theorem 8.1.5
(The rolling-row invariant)
In LCS_ROW, during the row for the th symbol of , at the start of the iteration for we have dp[j] , dp[j-1] and diagonal . At the end of the row, dp[j] for every .
Proof
(Induction over rows and columns)
Before the first row, dp holds . At the start of each row diagonal is , and dp[0] never changes. Suppose the three facts hold at iteration . Saving old dp[j] before overwriting lets the update compute exactly the recurrence: on a match it gives diagonal , and otherwise the maximum of dp[j] and dp[j-1] . So the new dp[j] is , and assigning diagonal = old supplies , the diagonal needed at iteration . Meanwhile dp[j+1] still holds and the new dp[j] is , which restores the three facts.
The row storage is , and nonempty-input time remains . Interchanging the two inputs if necessary makes m their smaller length. But returning this last row alone does not return the full table's predecessor choices.
Counterexample mode
A newly written diagonal can reuse the same symbol twice
Take X=A, Y=AA. The correct final row is [0,1,1].
If one assigns diagonal = dp[j] after updating the cell, instead
of assigning the saved old, the first match carries diagonal 1
to the second match. The row becomes [0,1,2].
That would use the single X symbol twice, violating strictly increasing indices. Saving the old diagonal is a correctness requirement, not a minor storage preference.
Split an optimal alignment at a boundary
Divide X into a left part of length and a right part . For each Y boundary , define
The intervals in this notation are zero-based and half-open. F comes from one forward row. For B, compute a row G on the reversed and reversed Y; then . Reversing both sequences reverses a common subsequence and preserves its length.
Theorem 8.1.6
(The split boundary preserves the optimal length)
For this fixed split of X,
Proof
(Cut a whole alignment, then concatenate two partial alignments)
In any common-subsequence alignment, matches using precede those using . Their Y indices are also increasing, so choose a boundary j between these two groups of Y indices. If a group is empty, the corresponding end boundary is available. The left group's length is at most F[j], and the right group's at most B[j]. Thus the whole optimum is no larger than the displayed maximum.
Conversely, for any j, concatenate an optimal left alignment with an optimal right alignment. Both X intervals and both Y intervals are ordered and disjoint, so the result is a valid alignment of length F[j]+B[j]. This gives the reverse bound and proves equality.
Reconstruct by divide and conquer
The split identity gives a Hirschberg-style reconstruction. Treat substrings and reversals as indexed views of the original inputs, rather than copied strings. Append symbols to one shared output buffer:
APPEND_LCS(X, Y, output):
n = length(X)
m = length(Y)
if n == 0 or m == 0:
return
if n == 1:
if X[0] occurs in Y:
append X[0] to output
return
h = n // 2
F = LCS_ROW(X[0:h], Y)
G = LCS_ROW(reverse(X[h:n]), reverse(Y))
j = smallest index maximizing F[j] + G[m-j]
release F and G
APPEND_LCS(X[0:h], Y[0:j], output)
APPEND_LCS(X[h:n], Y[j:m], output)
Empty inputs and the one-symbol case are solved directly. Otherwise choose a maximizing boundary and reconstruct the two smaller problems. Their concatenation is optimal by the split theorem and induction. Appending the left answer before the right preserves sequence order. The smallest-j tie rule is deterministic, but it need not match the full table's up-on-tie output.
Worked example 8.1.7
(Splitting ABAB and BABA at the middle of X)
For ABAB and BABA, split X as AB and AB:
| Boundary j | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| F[j] | 0 | 1 | 1 | 2 | 2 |
| B[j] | 2 | 2 | 1 | 1 | 0 |
| Sum | 2 | 3 | 2 | 3 | 2 |
The first maximizing boundary is j=1. The left answer is B from
AB and B; the right answer is AB from AB and ABA.
Concatenation gives BAB, an optimum different from the earlier traceback.
Worked example 8.1.8
(Empty input and a one-symbol first sequence)
For AB and empty, LCS_ROW has , so dp is [0] and the length is ; APPEND_LCS returns at its first test without appending anything. For C and ACC, the one-symbol branch applies. LCS_ROW gives [0,0,1,1]: both occurrences of C in match the single C of , but the second match reuses the saved diagonal , not the new value, so the length is . APPEND_LCS appends one C, not two. For D the same input gives [0,0,0,0] and nothing is appended.
Charge for recomputation, recursion and output separately
Theorem 8.1.9
(Cost of the divide-and-conquer reconstruction)
For nonempty inputs with , APPEND_LCS runs in time and auxiliary space, plus for an output of length .
Proof
(Geometric area bound and live rows)
At a non-base subproblem of lengths , , the two row computations together cost . Scanning the b+1 split scores costs , so the total remains . Its children have first lengths at most for , and their second lengths sum to b. Hence their total length-product area is at most . Summing this geometric bound over recursion levels gives work for nonempty inputs. A one-symbol leaf scans its Y view in time equal to its area; empty-child and call overhead is , also within when m is positive. Initially empty inputs return immediately.
The two score rows use memory. Releasing them before recursing prevents parent rows from remaining live on the recursion stack. The first input is halved each time, so control frames use space. After initially making , the stated implementation has auxiliary space for nonempty inputs, plus output storage for answer length . This separates linear row storage from the stack cost. Copied substrings, retained parent rows or repeatedly concatenated immutable output strings would require a different implementation-cost analysis.
An insertion/deletion distance is another view of the same optimum
Theorem 8.1.10
(Insertion and deletion distance)
If the allowed edits are single-symbol insertions and deletions, the minimum number of edits turning into is
Proof
(Keep a longest common subsequence)
Let . Keep a longest common subsequence, delete the other symbols, then insert the missing symbols: this attains the bound. Conversely, original symbols surviving an edit script appear in both sequences in order, so their count k is at most . At least n-k original symbols are deleted and at least m-k final symbols are inserted, requiring at least edits. This proves equality even if a proposed script wastes extra edits.
Unit-cost substitution is a different operation. For A and B,
the LCS length is 0 and the insertion/deletion distance is 2, but a
single substitution costs 1. The formula must be paired with its
specified edit model.
No algorithm with exponent below two is known for general inputs, and the question is tied to a hardness conjecture.
A natural next question
Can the quadratic table be avoided?
No algorithm with exponent below two is known for general inputs, and the question is tied to a hardness conjecture.
Every method in this unit takes time proportional to . For general inputs of equal length , no algorithm running in time for a fixed is known. A widely studied hardness conjecture would rule such an algorithm out, but that conjecture lies outside this course. The table method is therefore the standard answer, not a proved optimum.
Common mistakes
Common mistake
(Mixing up subsequence and substring)
For ABC and AC the longest common subsequence is AC, of length , but the longest common contiguous substring has length (A or C). The recurrence above is for subsequences; a substring version must reset to at a mismatch instead of taking a maximum.
Common mistake
(Following only one predecessor on a mismatch)
When , both and are candidates. For BA and B, the last symbols differ at . Using only gives , but is larger, and the true value is .
Common mistake
(Expecting a sequence from the final row)
The last row of LCS_ROW on ABAB and BABA is [0,1,2,3,3]. It gives the optimal length , but it is consistent with both ABA and BAB and records no predecessor choices. A reconstruction needs either the full table or the divide-and-conquer recomputation.
Solved exercises
Quick check
(Preserve a row's old information)
Run the rolling row for X=A, Y=AA. Give old, diagonal
and the updated cell at each inner iteration. What invariant is broken
by carrying the updated cell as the next diagonal?
Solution · Answer
Initially dp is [0,0,0] and diagonal is 0. At j=1, old is 0,
the cell becomes 1, and diagonal is set to old=0. At j=2, old is
again 0, the cell becomes 1, and diagonal stays 0. The final row
is [0,1,1]. Carrying the new first cell would set diagonal to 1
and then produce 2, although an LCS cannot be longer than the
one-symbol input. The diagonal must belong to the previous row.
Quick check
(Ties do not imply a unique LCS)
Trace the worked full table for ABAB and BABA with the shown
up-on-tie policy. Give the matched positions. How can a different
choice at the final tie produce another optimal sequence?
Solution · Answer
Move up from (4,4) to (3,4), then take matching pairs (3,4),
(2,3), (1,2), collecting A,B,A backwards. The result is
ABA. Moving left at the final tie instead reaches (4,3), then
uses pairs (4,3), (3,2), (2,1), giving BAB after reversal.
Both have length 3. The table establishes optimal length while the
tie policy selects one witness.
Quick check
(Find a divide-and-conquer split)
Take X=ABC, Y=ACB and split X into A and BC.
Compute F[j], B[j] and their sums for j=0,1,2,3. Which boundary
does the smallest-j policy select, and what optimal sequence can result?
Solution · Answer
F is [0,1,1,1]; B is [1,1,1,0]; the sums are
[1,2,2,1]. Choose j=1, assigning A versus A to the
left and BC versus CB to the right. The left contributes A;
the recursive smallest-j rule can contribute C on the right, giving
AC. Boundary j=2 could instead give AB. Both length-two
answers meet the proved maximum; no length-three common subsequence
exists because the two three-symbol strings differ in order.
Quick check
(State which edit operation is permitted)
Use LCS length to find the insertion/deletion distance from ABC
to AC, and give a script attaining it. Why does the same formula
not give unit-substitution distance from A to B?
Solution · Answer
The LCS AC has length 2, so the distance is ;
delete B. For A and B, LCS length is 0, so deleting A and
inserting B costs 2. If substitution is allowed at cost 1, replacing
A by B is cheaper. That added operation changes the optimization
problem, so it does not contradict the insertion/deletion theorem.