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

Failure function — where it appears

For each prefix of a pattern, the longest proper suffix of it that is also a prefix, which lets a matcher resume without re-reading a character. It is what lets a matcher resume without re-reading a character, and it is computed from the pattern alone in time linear in its length.

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

characters examinedNaive scan520,25663.51 per text characterKnuth–Morris–Pratt16,3211.99 per text characterBoyer–Moore–Horspool8,1290.99 per text characterRabin–Karp00.00 per text characterone unit = one character comparisonone matcher read no characters at all

The shift the pattern already knows

On a text of 8,192 characters the naive scan examines 520,256 of them and Knuth–Morris–Pratt examines 16,321 — a factor of 32, and 16,321 is 99.6% of the 2n that no input can push it past. On ordinary random text the same two algorithms examine 20,862 and 20,833. Both measurements are of the same pair of algorithms and only one of them is the reason anybody uses the second.

text · Symbol roothseirhesssolid: a transition on a character · dashed: a suffix or failure link10 states for 12 pattern characters

One pass for every pattern at once

Sixty-four patterns, one text, twenty thousand characters read. Running this site's KMP once per pattern reads 1,595,445 — and an implementation missing one kind of link finds fewer occurrences, reads exactly as much, and looks better on every counter.

text · Automaton

Named alongside it

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

Amortised analysisCharacter comparisonAho-corasickAlphabetAlphabet sizeAutomatonBacktrackingIndexKmpMeasured countNaive scanPattern matching

All concepts