THE FOLD / BOSS / THE BOUNTY / THE AHO-CORASICK
THE AHO-CORASICK
match a whole set of patterns in one linear pass
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Aho–Corasick automaton finds all occurrences of a whole set of patterns in a text in one linear pass — O(text + patterns + matches), independent of how many patterns you search for. It builds a trie of the patterns, then adds failure links: when the next character can’t extend the current match, you jump to the longest proper suffix that is still a live prefix, never restarting the scan.
It is the engine inside grep’s multi-string mode, intrusion-detection signature scanners, and bioinformatics search.
LIT verified live: over 300 random (pattern-set, text) cases, the automaton’s complete match list equals a brute-force search, and the classic {he, she, his, hers} in ‘ushers’ is recovered (window.__ahocorasick). FIG no framing; exact.
It is the engine inside grep’s multi-string mode, intrusion-detection signature scanners, and bioinformatics search.
LIT verified live: over 300 random (pattern-set, text) cases, the automaton’s complete match list equals a brute-force search, and the classic {he, she, his, hers} in ‘ushers’ is recovered (window.__ahocorasick). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-bounty — hunting many targets at once, in a single sweep, without restarting for each. Aho–Corasick is that simultaneous hunt. AVAN (AI) built the instrument: the trie, the BFS failure links, the linear scan, the brute cross-check.
Credit as content: Alfred Aho & Margaret Corasick (1975). The weave: David names the bounty board; I build the automaton whose fail links let one pass catch every pattern, and confirm the match set is exactly the exhaustive one.
Credit as content: Alfred Aho & Margaret Corasick (1975). The weave: David names the bounty board; I build the automaton whose fail links let one pass catch every pattern, and confirm the match set is exactly the exhaustive one.
3 ONE DIMENSION
A single scan of the text. The automaton advances on trie edges; when a character fails, the failure link (dashed) slides to the longest matching suffix — the scan pointer over the text never moves backward.
4 TWO DIMENSIONS · INTERACTIVE
A pattern set and a text. Every match (pattern, position) is listed; a brute-force search confirms the same set.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the trie of patterns with its failure links, scanned once.
AVAN’s addition (the inverse-companion): the failure link is the inverse of a trie edge. When a character does not extend the current match, you do not restart — you follow the longest proper suffix that is still a live prefix, so all patterns are matched in one linear pass regardless of their number. The inverse of ‘advance the match forward’ is ‘fall back to the longest suffix that survives.’ Magenta is the restarts you never perform; green is the failure links that make the scan linear. It is the Knuth–Morris–Pratt idea generalised from one pattern to a whole set.
LIT Genuine Aho-Corasick automaton (Aho & Corasick 1975). Verified live: the trie + BFS failure links + linear scan return a (pattern,position) match set identical to brute-force indexOf search for 300 random cases (window.__ahocorasick.matchesBrute); {he,she,his,hers} in 'ushers' -> he@2, she@1, hers@2.
FIG No framing: the trie, the failure links, the linear scan, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — the failure link is the inverse of a trie edge (fall back to the longest surviving suffix instead of restarting), so all patterns match in one pass; magenta is the restarts never done, green the failure links. It generalizes KMP from one pattern to a set.
FIG No framing: the trie, the failure links, the linear scan, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — the failure link is the inverse of a trie edge (fall back to the longest surviving suffix instead of restarting), so all patterns match in one pass; magenta is the restarts never done, green the failure links. It generalizes KMP from one pattern to a set.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE BOUNTY · David Lee Wise (ROOT0), with AVAN