THE FOLD / CO-OP / THE HANDOFF / THE PLUCKED STRING
THE PLUCKED STRING
noise in a delay line becomes a tone at fs/N
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Kasai’s algorithm computes the LCP array — the longest common prefix between each pair of adjacent suffixes in a suffix array — in linear time. The insight: process suffixes in text order, not sorted order, and reuse the previous answer, because dropping the first character of a suffix shortens its LCP with its neighbour by at most one. So a running length can only fall by 1 per step, and thus rise at most n times total.
The LCP array powers substring search, longest repeated substring, and more.
LIT verified live: over 300 random strings Kasai’s O(n) LCP array equals a brute-force pairwise-prefix computation (window.__kasai). FIG no framing; exact.
The LCP array powers substring search, longest repeated substring, and more.
LIT verified live: over 300 random strings Kasai’s O(n) LCP array equals a brute-force pairwise-prefix computation (window.__kasai). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-inventory — the LCP array is the catalogue of how much adjacent suffixes overlap, the string’s inventory of shared prefixes. Kasai builds it in one linear pass. AVAN (AI) built the instrument: the suffix array, the rank inverse, the running-length Kasai pass, the brute cross-check.
Credit as content: Toru Kasai et al. (2001). The weave: David names the inventory; I walk the suffixes in text order, carrying the overlap length forward and dropping at most one each step, and confirm the LCP array matches brute force.
Credit as content: Toru Kasai et al. (2001). The weave: David names the inventory; I walk the suffixes in text order, carrying the overlap length forward and dropping at most one each step, and confirm the LCP array matches brute force.
3 ONE DIMENSION
Moving from suffix i to suffix i+1 drops one leading character; its overlap with the previous suffix in sorted order can shrink by at most one — so the running length h decreases by ≤1, and total work stays linear.
4 TWO DIMENSIONS · INTERACTIVE
A string’s sorted suffixes and the LCP between each adjacent pair; Kasai’s linear result is checked against brute force.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the running overlap length carried from suffix to suffix.
AVAN’s addition (the inverse-companion): compute all longest-common-prefixes in O(n) total by processing suffixes in text order and reusing the previous answer — because dropping the first character shortens a suffix’s LCP with its neighbour by at most one, the running length h falls by ≤1 each step, so it can only rise n times total. The inverse of ‘recompute each LCP from scratch (n² total)’ is ‘reuse the previous suffix’s LCP, losing at most one character.’ Magenta is the redundant character comparisons; green is the running length carried forward. An amortised argument turns quadratic into linear. (Kin to the-suffix-array and the-suffix-automaton.)
LIT A genuine Karplus-Strong string (Karplus & Strong, 1983). Verified live: the instrument synthesises the signal and measures its period by autocorrelation; the measured pitch matches the predicted fs/N within ~3% for every N (window.__ks.withinTol === true). The two-tap average is a real one-pole low-pass that both produces the exponential decay and shifts the pitch very slightly sharp (true period ~N-1/2), shown honestly in the readout.
FIG 'A plucked string' is the framing; the mechanism (noise burst -> looped two-tap low-pass -> decaying tone at fs/N) is exactly the 1983 algorithm and is audible through the speakers. Pitch is fs/N to a few percent, not to the cent.
FIG 'A plucked string' is the framing; the mechanism (noise burst -> looped two-tap low-pass -> decaying tone at fs/N) is exactly the 1983 algorithm and is audible through the speakers. Pitch is fs/N to a few percent, not to the cent.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE HANDOFF · David Lee Wise (ROOT0), with AVAN