Tools Suite

Dynamic programming

O(m · n)·O(m · n) space
Whole table

Drag to pan; pinch or Ctrl+scroll to zoom, which stops at the whole table; arrow keys pan once the picture has focus. The headers stay put while you pan.

the empty first prefix, the empty second prefix, not yet filledthe empty first prefix, column 1, ‘L’, not yet filledthe empty first prefix, column 2, ‘O’, not yet filledthe empty first prefix, column 3, ‘G’, not yet filledthe empty first prefix, column 4, ‘A’, not yet filledthe empty first prefix, column 5, ‘R’, not yet filledthe empty first prefix, column 6, ‘I’, not yet filledthe empty first prefix, column 7, ‘T’, not yet filledthe empty first prefix, column 8, ‘H’, not yet filledthe empty first prefix, column 9, ‘M’, not yet filledrow 1, ‘A’, the empty second prefix, not yet filledrow 1, ‘A’, column 1, ‘L’, not yet filledrow 1, ‘A’, column 2, ‘O’, not yet filledrow 1, ‘A’, column 3, ‘G’, not yet filledrow 1, ‘A’, column 4, ‘A’, not yet filledrow 1, ‘A’, column 5, ‘R’, not yet filledrow 1, ‘A’, column 6, ‘I’, not yet filledrow 1, ‘A’, column 7, ‘T’, not yet filledrow 1, ‘A’, column 8, ‘H’, not yet filledrow 1, ‘A’, column 9, ‘M’, not yet filledrow 2, ‘L’, the empty second prefix, not yet filledrow 2, ‘L’, column 1, ‘L’, not yet filledrow 2, ‘L’, column 2, ‘O’, not yet filledrow 2, ‘L’, column 3, ‘G’, not yet filledrow 2, ‘L’, column 4, ‘A’, not yet filledrow 2, ‘L’, column 5, ‘R’, not yet filledrow 2, ‘L’, column 6, ‘I’, not yet filledrow 2, ‘L’, column 7, ‘T’, not yet filledrow 2, ‘L’, column 8, ‘H’, not yet filledrow 2, ‘L’, column 9, ‘M’, not yet filledrow 3, ‘G’, the empty second prefix, not yet filledrow 3, ‘G’, column 1, ‘L’, not yet filledrow 3, ‘G’, column 2, ‘O’, not yet filledrow 3, ‘G’, column 3, ‘G’, not yet filledrow 3, ‘G’, column 4, ‘A’, not yet filledrow 3, ‘G’, column 5, ‘R’, not yet filledrow 3, ‘G’, column 6, ‘I’, not yet filledrow 3, ‘G’, column 7, ‘T’, not yet filledrow 3, ‘G’, column 8, ‘H’, not yet filledrow 3, ‘G’, column 9, ‘M’, not yet filledrow 4, ‘O’, the empty second prefix, not yet filledrow 4, ‘O’, column 1, ‘L’, not yet filledrow 4, ‘O’, column 2, ‘O’, not yet filledrow 4, ‘O’, column 3, ‘G’, not yet filledrow 4, ‘O’, column 4, ‘A’, not yet filledrow 4, ‘O’, column 5, ‘R’, not yet filledrow 4, ‘O’, column 6, ‘I’, not yet filledrow 4, ‘O’, column 7, ‘T’, not yet filledrow 4, ‘O’, column 8, ‘H’, not yet filledrow 4, ‘O’, column 9, ‘M’, not yet filledrow 5, ‘R’, the empty second prefix, not yet filledrow 5, ‘R’, column 1, ‘L’, not yet filledrow 5, ‘R’, column 2, ‘O’, not yet filledrow 5, ‘R’, column 3, ‘G’, not yet filledrow 5, ‘R’, column 4, ‘A’, not yet filledrow 5, ‘R’, column 5, ‘R’, not yet filledrow 5, ‘R’, column 6, ‘I’, not yet filledrow 5, ‘R’, column 7, ‘T’, not yet filledrow 5, ‘R’, column 8, ‘H’, not yet filledrow 5, ‘R’, column 9, ‘M’, not yet filledrow 6, ‘I’, the empty second prefix, not yet filledrow 6, ‘I’, column 1, ‘L’, not yet filledrow 6, ‘I’, column 2, ‘O’, not yet filledrow 6, ‘I’, column 3, ‘G’, not yet filledrow 6, ‘I’, column 4, ‘A’, not yet filledrow 6, ‘I’, column 5, ‘R’, not yet filledrow 6, ‘I’, column 6, ‘I’, not yet filledrow 6, ‘I’, column 7, ‘T’, not yet filledrow 6, ‘I’, column 8, ‘H’, not yet filledrow 6, ‘I’, column 9, ‘M’, not yet filledrow 7, ‘T’, the empty second prefix, not yet filledrow 7, ‘T’, column 1, ‘L’, not yet filledrow 7, ‘T’, column 2, ‘O’, not yet filledrow 7, ‘T’, column 3, ‘G’, not yet filledrow 7, ‘T’, column 4, ‘A’, not yet filledrow 7, ‘T’, column 5, ‘R’, not yet filledrow 7, ‘T’, column 6, ‘I’, not yet filledrow 7, ‘T’, column 7, ‘T’, not yet filledrow 7, ‘T’, column 8, ‘H’, not yet filledrow 7, ‘T’, column 9, ‘M’, not yet filledrow 8, ‘H’, the empty second prefix, not yet filledrow 8, ‘H’, column 1, ‘L’, not yet filledrow 8, ‘H’, column 2, ‘O’, not yet filledrow 8, ‘H’, column 3, ‘G’, not yet filledrow 8, ‘H’, column 4, ‘A’, not yet filledrow 8, ‘H’, column 5, ‘R’, not yet filledrow 8, ‘H’, column 6, ‘I’, not yet filledrow 8, ‘H’, column 7, ‘T’, not yet filledrow 8, ‘H’, column 8, ‘H’, not yet filledrow 8, ‘H’, column 9, ‘M’, not yet filledrow 9, ‘M’, the empty second prefix, not yet filledrow 9, ‘M’, column 1, ‘L’, not yet filledrow 9, ‘M’, column 2, ‘O’, not yet filledrow 9, ‘M’, column 3, ‘G’, not yet filledrow 9, ‘M’, column 4, ‘A’, not yet filledrow 9, ‘M’, column 5, ‘R’, not yet filledrow 9, ‘M’, column 6, ‘I’, not yet filledrow 9, ‘M’, column 7, ‘T’, not yet filledrow 9, ‘M’, column 8, ‘H’, not yet filledrow 9, ‘M’, column 9, ‘M’, not yet filledthe empty second prefix—0column 1, ‘L’L1column 2, ‘O’O2column 3, ‘G’G3column 4, ‘A’A4column 5, ‘R’R5column 6, ‘I’I6column 7, ‘T’T7column 8, ‘H’H8column 9, ‘M’M9the empty first prefix—0row 1, ‘A’A1row 2, ‘L’L2row 3, ‘G’G3row 4, ‘O’O4row 5, ‘R’R5row 6, ‘I’I6row 7, ‘T’T7row 8, ‘H’H8row 9, ‘M’M9→ second↓ first

The table has 10 rows and 10 columns, and nothing has been worked out yet. Row zero and column zero stand for the empty prefix, which has nothing in common with anything.

The table has 10 rows and 10 columns, and nothing has been worked out yet. Row zero and column zero stand for the empty prefix, which has nothing in common with anything.
Answer so far—

L(i, j) = a[i] = b[j] ? 1 + L(i−1, j−1) : max( L(i−1, j), L(i, j−1) )

  1. 1fill the first row and the first column with zeroes: nothing in common with nothing
  2. 2the two characters match, so take the cell diagonally back and add one
  3. 3the two characters differ, so take the larger of the cell above and the cell to the left
  4. 4write it into the cell
  5. 5walk back, stepping diagonally wherever the characters matched and collecting them
  6. 6stop: the bottom-right cell is the length, and the walk back is the subsequence
Cells filled
0
Cells read
0
Values written
0

Complexity

BestO(m · n)
AverageO(m · n)
WorstO(m · n)
Extra spaceO(m · n)
2 · m × n at n=100 predicts 200; this run took 0.

Longest common subsequence

A subsequence keeps the order of the characters but need not keep them adjacent. The table holds, for every pair of prefixes, the length of their longest common subsequence. If the two characters at the end of the prefixes are the same, that character can be used: the answer is one more than the answer for both prefixes shortened by one. If they differ, one of the two characters must be dropped, and the answer is the better of dropping either.

Its recurrence

L(i, j) = a[i] = b[j] ? 1 + L(i−1, j−1) : max( L(i−1, j), L(i, j−1) )

When it is the right choice

Anywhere two sequences have to be aligned rather than matched: diff tools, version control merges, spelling correction, comparing DNA. A file diff is exactly this algorithm with lines for characters — the lines it reports as unchanged are the longest common subsequence, and everything else is an insertion or a deletion.

How it works

Worth noticing

Cost

Best
O(m · n)
Average
O(m · n)
Worst
O(m · n)
Extra space
O(m · n)
Table
two dimensions
Accepts
up to 16 characters in each string

The limits are pedagogical rather than technical: this tool keeps the whole table in every recorded step, so the shape of the table sets the size of the trace directly, and a run has to stay short enough to sit and watch. An input that would take more than three thousand steps on this algorithm is refused before a single step is generated, from a formula in the input sizes rather than by running it and finding out.

An unfilled cell is drawn differently from a cell holding a zero — no fill, a dashed outline, and no number at all — because early in a run that difference is most of the picture.

Worth comparing

All dynamic programming algorithms