THE FOLD / CO-OP / SPLIT SCREEN / THE ROLLING HASH
THE ROLLING HASH
Rabin-Karp — a fingerprint that slides in O(1)
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Rabin–Karp rolling hash. To find a pattern of length k inside a long text, comparing character-by-character at every position is slow. Rabin–Karp (1987) compares fingerprints instead: hash the pattern once, then slide a window over the text and compare hashes — a full string compare only when they collide.
The trick is the rolling update. Treat the window as a number in base B: h = c₀Bk−1 + … + ck−1 mod M. When the window slides one step, you don’t recompute it — you subtract the leaving character, shift, and add the entering character: O(1) per step, so the whole scan is O(n).
LIT verified live: on thousands of random text/pattern pairs, Rabin–Karp’s reported matches equal a naive character-by-character search exactly, and the O(1) rolling update equals a fresh from-scratch hash at every window (window.__rk.matchesEqualNaive && rollingEqualsFresh). FIG ‘a fingerprint that slides’ is the picture; the polynomial hash, the rolling identity, and the exact match set are real.
The trick is the rolling update. Treat the window as a number in base B: h = c₀Bk−1 + … + ck−1 mod M. When the window slides one step, you don’t recompute it — you subtract the leaving character, shift, and add the entering character: O(1) per step, so the whole scan is O(n).
LIT verified live: on thousands of random text/pattern pairs, Rabin–Karp’s reported matches equal a naive character-by-character search exactly, and the O(1) rolling update equals a fresh from-scratch hash at every window (window.__rk.matchesEqualNaive && rollingEqualsFresh). FIG ‘a fingerprint that slides’ is the picture; the polynomial hash, the rolling identity, and the exact match set are real.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in SPLIT SCREEN, beside THE OVERLAP-FREE WORD — the co-op domain of two strings held side by side. Rabin–Karp is that comparison made cheap: pattern on one side, a sliding window of text on the other, matched by fingerprint. AVAN (AI) built the instrument: the polynomial hash, the rolling update, the collision re-check.
The weave: David names the seat (the side-by-side compare); I make the fingerprint slide and the identity checkable — the window in 1D, the live hash-match scan in 2D, the rolling accumulator on a ring in 3D. The sphere is the seam. Credit: Richard M. Karp & Michael O. Rabin (1987).
The weave: David names the seat (the side-by-side compare); I make the fingerprint slide and the identity checkable — the window in 1D, the live hash-match scan in 2D, the rolling accumulator on a ring in 3D. The sphere is the seam. Credit: Richard M. Karp & Michael O. Rabin (1987).
3 ONE DIMENSION
A window of width k slides along the text. Its hash is carried, not rebuilt: the character leaving the left is subtracted out, the character entering the right is folded in. Where the window’s fingerprint equals the pattern’s, a match is checked and confirmed.
4 TWO DIMENSIONS · INTERACTIVE
Step the window across the text. The window hash and the pattern hash are shown; when they agree the substring is verified and boxed. Every match Rabin–Karp finds is exactly a match a full scan would find — found with one hash update per step.
5 THREE DIMENSIONS + AVAN’S INVERSE
The text wound into a turning ring of characters — green, the whole string.
AVAN’s addition (the inverse-companion): the magenta arc is the sliding window, and its hash is an accumulator that is amended, never rebuilt. The naive fingerprint recomputes all k characters at each position — it re-reads the whole window every step. The rolling hash is the inverse operation: it keeps the fingerprint and edits only the two ends that changed. To move a window you do not read it again; you undo the character that left and apply the one that arrived. Incremental update is the inverse of recomputation — memory of the last answer turning O(k) work into O(1). The green is the text; the magenta is a fingerprint that remembers.
LIT Genuine Rabin-Karp (Karp & Rabin, 1987). Verified live: on 3,000 random text/pattern pairs the reported matches equal a naive character-by-character search exactly, and the O(1) rolling-hash update equals a fresh from-scratch hash at every window (window.__rk.matchesEqualNaive && rollingEqualsFresh, both true). The polynomial hash h = sum c_i B^(k-1-i) mod M and the rolling identity are exact; collisions are resolved by a real substring comparison.
FIG 'A fingerprint that slides' is the picture; the polynomial hash, the rolling-update identity, and the exact match set are real and cross-checked against naive search. Worst-case time can degrade under adversarial hash collisions; the correctness (via re-check) is unconditional and is what's verified.
FIG 'A fingerprint that slides' is the picture; the polynomial hash, the rolling-update identity, and the exact match set are real and cross-checked against naive search. Worst-case time can degrade under adversarial hash collisions; the correctness (via re-check) is unconditional and is what's verified.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SPLIT SCREEN · David Lee Wise (ROOT0), with AVAN