THE FOLD / LOOT / THE INVENTORY / THE SUFFIX AUTOMATON
THE SUFFIX AUTOMATON
the smallest machine recognizing every substring, O(n) states
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The suffix automaton is the smallest deterministic machine that recognises exactly the substrings of a string — and it has only O(n) states for a length-n string, even though the string has up to n(n+1)/2 substrings. Every substring is a path from the start; end-positions that behave identically are merged into one state via ‘suffix links’.
It answers substring queries, counts distinct substrings, and finds longest common substrings in linear time.
LIT verified live: over 300 random strings the automaton’s distinct-substring count — Σ(len − len[link]) over states — equals a brute-force count, and it accepts substrings while rejecting non-substrings (window.__suffixautomaton). FIG no framing; exact.
It answers substring queries, counts distinct substrings, and finds longest common substrings in linear time.
LIT verified live: over 300 random strings the automaton’s distinct-substring count — Σ(len − len[link]) over states — equals a brute-force count, and it accepts substrings while rejecting non-substrings (window.__suffixautomaton). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-inventory — a compact catalogue of every piece a string contains, every substring indexed in linear space. The suffix automaton is that inventory. AVAN (AI) built the instrument: the online construction with suffix links and clones, the distinct-count formula, the membership check.
Credit as content: Blumer et al. (1985), the ‘DAWG’. The weave: David names the inventory; I build the minimal substring machine one character at a time and confirm it counts and recognises every substring exactly.
Credit as content: Blumer et al. (1985), the ‘DAWG’. The weave: David names the inventory; I build the minimal substring machine one character at a time and confirm it counts and recognises every substring exactly.
3 ONE DIMENSION
Each state covers a range of substring lengths [len[link]+1 … len]; summing those ranges over all states counts every distinct substring — a linear structure holding a quadratic set.
4 TWO DIMENSIONS · INTERACTIVE
A string, its suffix automaton (states and transitions), and its distinct-substring count checked against brute force.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the O(n) states whose paths are all the substrings.
AVAN’s addition (the inverse-companion): the smallest machine recognising exactly the substrings has only O(n) states. Every substring is a path, and end-positions that behave identically are merged into one state, so a linear automaton encodes a quadratic number of substrings. The inverse of ‘enumerate the substrings’ is ‘the minimal automaton whose paths are the substrings.’ Magenta is the O(n²) substrings spelled out; green is the O(n) states that generate them. The distinct count Σ(len − len[link]) falls straight out of the structure.
LIT Genuine suffix automaton / DAWG (Blumer et al. 1985). Verified live: the online construction's distinct-substring count Sigma(len - len[link]) over states equals a brute-force substring-set count, and path traversal accepts substrings and rejects non-substrings, for 300 random strings (window.__suffixautomaton.distinctMatches && .membership).
FIG No framing: the online construction with suffix links and clones, the distinct-count formula, and the membership check run in-browser and are exact. The AVAN inverse is honest — the minimal automaton merges identically-behaving end-positions so O(n) states encode a quadratic number of substrings, and the distinct count falls out as Sigma(len - len[link]); magenta is the O(n^2) substrings spelled out, green the O(n) states.
FIG No framing: the online construction with suffix links and clones, the distinct-count formula, and the membership check run in-browser and are exact. The AVAN inverse is honest — the minimal automaton merges identically-behaving end-positions so O(n) states encode a quadratic number of substrings, and the distinct count falls out as Sigma(len - len[link]); magenta is the O(n^2) substrings spelled out, green the O(n) states.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE INVENTORY · David Lee Wise (ROOT0), with AVAN