THE FOLD / CO-OP / THE BROADCAST / THE RABIN-KARP
THE RABIN-KARP
string search by a rolling hash
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Rabin–Karp algorithm finds a pattern in text using a rolling hash: it hashes the pattern once, then slides a window over the text, updating the window’s hash in O(1) per step by removing the leaving character and adding the entering one — polynomial hashing modulo a large prime. Only when hashes match does it verify character-by-character. It shines at multi-pattern search and plagiarism detection.
LIT verified live: over 300 random text/pattern pairs, the rolling-hash match positions (with match verification) exactly equal a brute-force scan (window.__rabinkarp). FIG no framing; exact (hashes filter, then confirm).
LIT verified live: over 300 random text/pattern pairs, the rolling-hash match positions (with match verification) exactly equal a brute-force scan (window.__rabinkarp). FIG no framing; exact (hashes filter, then confirm).
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-broadcast — scanning a stream for a signal, cheaply, one character at a time. Rabin–Karp is that scan. AVAN (AI) built the instrument: the polynomial hash, the O(1) roll (remove-add), the on-match verification, and the brute cross-check.
Credit as content: Michael Rabin & Richard Karp (1987). The weave: David names the broadcast; I roll a modular hash across the text and, on every hash hit, confirm the characters — matching a direct scan exactly.
Credit as content: Michael Rabin & Richard Karp (1987). The weave: David names the broadcast; I roll a modular hash across the text and, on every hash hit, confirm the characters — matching a direct scan exactly.
3 ONE DIMENSION
Slide the window one step: subtract the departing character’s weighted value, multiply by the base, add the arriving character. The hash updates in O(1) — no re-reading the window.
4 TWO DIMENSIONS · INTERACTIVE
A text and a pattern; the rolling hash flags candidate positions and confirms matches, checked against a brute scan.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: matches found by a rolling fingerprint.
AVAN’s addition (the inverse-companion): search for a pattern by a rolling fingerprint — update the window’s hash in O(1) as it slides, and only compare characters when fingerprints agree. The inverse of ‘re-read every window fully to compare’ is ‘keep a rolling hash, verify only on a hit.’ Magenta is the full comparisons skipped at non-matching windows; green is the confirmed matches. Search by a fingerprint that rolls.
LIT Genuine Rabin-Karp rolling-hash search (Rabin & Karp 1987). Verified live: over 300 random text/pattern pairs, the polynomial rolling hash (updated O(1) per slide) with on-match character verification returns exactly the same match positions as a brute-force scan (window.__rabinkarp.matchesBrute).
FIG No framing: the polynomial hash, the O(1) roll (remove-add), the on-match verification, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — a rolling fingerprint updated in O(1) as the window slides, with character comparison only on a hash hit, replaces full re-reading of every window; magenta is the comparisons skipped at non-matching windows, green the confirmed matches. Search by a fingerprint that rolls.
FIG No framing: the polynomial hash, the O(1) roll (remove-add), the on-match verification, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — a rolling fingerprint updated in O(1) as the window slides, with character comparison only on a hash hit, replaces full re-reading of every window; magenta is the comparisons skipped at non-matching windows, green the confirmed matches. Search by a fingerprint that rolls.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE BROADCAST · David Lee Wise (ROOT0), with AVAN