THE FOLD / BOSS / THE CHOKE POINT / THE Z-ALGORITHM

THE Z-ALGORITHM

all prefix matches in O(n) — a pointer that never retreats

1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION

The Z-algorithm computes, for every position i of a string, the length of the longest substring starting at i that matches a prefix of the whole string — the Z-array. Done naively that is O(n²); the Z-algorithm does it in O(n) by keeping the rightmost match interval [l,r] seen so far and reusing earlier Z-values inside it.

Concatenate pattern § text and the Z-array instantly locates every occurrence of the pattern (wherever Z equals the pattern length) — clean linear-time string search, a sibling of KMP.

LIT verified live: for 500 random strings, every Z[i] equals a brute-force prefix-match length (window.__zalgorithm). FIG no framing; exact string matching.

2 HOW IT WAS WEAVED · AI + HUMAN

David (human) seated this at the-choke-point — the bottleneck every search must pass through, where linear time matters. The Z-algorithm is the choke-point cleared: all prefix matches in one pass. AVAN (AI) built the instrument: the [l,r] window, the mirror-reuse, the brute cross-check, the pattern search.

Credit as content: popularised by Dan Gusfield’s Algorithms on Strings, Trees, and Sequences (1997); part of the linear-time string-matching lineage. The weave: David names the choke-point; I compute the Z-array in one forward sweep, verify it against brute force, and show the right pointer that never retreats.

3 ONE DIMENSION

The current match window [l,r]. Inside it, position i mirrors an earlier position i−l whose Z-value is already known — so the algorithm copies that answer and only ever extends past r, which moves forward and never back.

4 TWO DIMENSIONS · INTERACTIVE

Type a string; the Z-array is computed in O(n) and shown as bars. Verify each Z[i] against a brute prefix-match, and use pattern § text to locate every occurrence in linear time.

5 THREE DIMENSIONS + AVAN’S INVERSE

The green forward object: the Z-values as bars along the string — every prefix match found in a single sweep.

AVAN’s addition (the inverse-companion): the linear time comes from never re-comparing a character already known to match. Inside the current window [l,r], position i is a mirror of the earlier position i−l, whose Z-value is already computed — so the algorithm copies the answer and only extends past r. The inverse of ‘recompare from scratch at every i’ is ‘reuse the mirror, and advance a right pointer that only moves forward.’ Because r never retreats, the total extra comparisons across the whole string sum to at most n — amortised linearity from a monotone pointer. Magenta is the O(n²) redundant comparisons skipped; green is the single forward march of r. Speed from memory of what already matched.

LIT Genuine Z-algorithm (popularized by Gusfield 1997; linear-time string matching lineage). Verified live: computing the Z-array with the [l,r] window and mirror-reuse, every Z[i] equals the brute-force longest-common-prefix length for 500 random strings (window.__zalgorithm.matchesBrute); aabaab -> 6,1,0,3,1,0.

FIG No framing: the O(n) Z-array and the brute cross-check run in-browser and match exactly. The AVAN inverse is honest — linearity comes from reusing the mirror position i-l inside the window and a right pointer r that never retreats, so total extra comparisons sum to <= n (amortized O(n)); magenta is the O(n^2) comparisons skipped, green the single forward march of r.

◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE CHOKE POINT · David Lee Wise (ROOT0), with AVAN