Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Longest common subsequence — where it appears

The longest sequence of characters appearing in order, though not necessarily together, in two strings. Its table has the same shape as an edit distance's and one difference that matters: only the cells where the characters agree can lengthen anything.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

—gactacgat—gattacagt0123456789101234567821012345673211123456432212345554332123456543321234765443222387655432339876554333one unit = one subproblem given a value100 cells, 100 held at once

A distance that is a path through a grid

How far apart two strings are is a shortest-path problem on a grid whose every edge is drawn by the recurrence — and finding a string in a text costs 4,988 character comparisons where measuring how far it is from one costs 96,000.

text · Distance —gactacgat—gattacagt112223334244352461647one unit = one subproblem given a value21 matching pairs, 21% of the rectangle

The cells that were never worth having

Two three-hundred-character strings over twenty-six letters give a table of 90,601 cells, and 3,421 of them are pairs of positions whose characters agree. Only those can lengthen anything. A method that enumerates exactly those computes a twenty-sixth of the table — and on a two-letter alphabet it computes half of it and is worse than the table it replaced.

tables · Table

Named alongside it

The objects these essays reach for when they reach for this one.

Dynamic programmingSubproblemAlignmentAlphabet sizeApproximate matchingBinary searchCharacter comparisonComplexity classCost modelEdit distanceLevenshteinMeasured count

All concepts