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

Suffix automaton — where it appears

The smallest deterministic machine accepting exactly the suffixes of a text, with at most 2n − 1 states however many substrings the text contains. Its state count is linear where the number of distinct substrings is quadratic, which is the whole reason the structure is worth building.

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

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 —1234152abcbcbccbsolid: a transition on a character · dashed: a suffix or failure link8 states ≤ 9, 9 transitions ≤ 11

Every substring, in fewer states than substrings

A text of 512 characters has 129,416 distinct substrings. A machine that recognises every one of them, and nothing else, needs 831 states — and the bound it is under, 2n − 1, is reached exactly by a string one line long.

structures · Automaton depth 0190.1%depth 19642.9%depth 24,92915.0%depth 37,00921.4%depth 48,47325.9%depth 56,24119.0%depth 63,31010.1%depth 71,2503.8%depth 84221.3%depth 91240.4%depth 10270.1%positions32,768 characters · 1172 phrasesmean 3.98

The number that would choose a cap

A depth histogram is one linear pass — 3.16 operations a character over thirty-two thousand of them — and it says the whole text sits at a mean depth of 3.98 with a worst of ten. Nobody prints it, and every choice of cap in this collection was made without it.

practice · Parse 11010³cap on the depthphrases9.8% more phrasesevery occurrence consideredthe earliest only4,096 charactersworst at cap 4

The cap an automaton cannot see

A state of a suffix automaton stands for a set of occurrences and hands back one of them. So a capped parse driven by it can ask whether the earliest occurrence is shallow enough and cannot ask whether any occurrence is — which costs up to 9.8% of the phrases, and only at the caps that bind.

bounds · Parse 1,00010⁴10⁵10⁶charactersoperationscharacter comparisonstransitions and linksrepetitive · 8 copies346 phrases at 8,192

The parse in one pass of the text

The same parse, phrase for phrase, from 1,324,336 character comparisons or from 25,420 transitions and suffix-link steps. One of those numbers grows with the text and the other grows with its square, and the difference is why every measurement about a depth cap here was taken on a few thousand characters.

text · Parse 11010⁴cap on the depthphrasesno capcap 165,536 characters · 16 copies26x at cap 1

What a quadratic construction was setting

A depth cap of one costs 90% of an 8,192-character text in phrases, and 86% of a 65,536-character one. The ladder's conclusions hold at thirty-two times the size — and the number the ladder could not reach, the deepest chain a real collection produces, turns out to be fourteen.

wrong · Parse

Named alongside it

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

Lempel zivMeasurementPhraseTrade offConstructionDepth capParseRepetitionAlphabetAmortised analysisAutomatonDefinition

All concepts