THE FOLD / LOOT / THE INVENTORY / THE KASAI
THE KASAI
the LCP array in linear time by reusing the last overlap
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 Genuine Kasai's algorithm (Kasai et al. 2001). Verified live: the text-order running-length LCP pass equals a brute-force pairwise longest-common-prefix computation over the suffix array for 300 random strings (window.__kasai.matchesBrute).
FIG No framing: the suffix array, the rank inverse, the running-length Kasai pass, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — processing suffixes in text order and reusing the previous LCP (which can only drop by one when the leading character is removed) makes the total work linear by an amortized argument; magenta is the redundant character comparisons, green the running length carried forward. Kin to the-suffix-array and the-suffix-automaton.
FIG No framing: the suffix array, the rank inverse, the running-length Kasai pass, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — processing suffixes in text order and reusing the previous LCP (which can only drop by one when the leading character is removed) makes the total work linear by an amortized argument; magenta is the redundant character comparisons, green the running length carried forward. Kin to the-suffix-array and the-suffix-automaton.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE INVENTORY · David Lee Wise (ROOT0), with AVAN