THE FOLD / CO-OP / SHARED MEMORY / THE MANACHER
THE MANACHER
longest palindrome in linear time — reflection is the memory
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Manacher’s algorithm finds the longest palindromic substring of a string in linear O(n) time — where the naive approach re-expands around every centre in O(n²). Its trick: as it scans, it keeps the rightmost palindrome found so far, and for any new centre inside it, the palindrome’s mirror position already tells you a guaranteed radius — so you never re-check what symmetry has proven.
A separator transform (inserting ‘#’ between characters) makes even- and odd-length palindromes uniform, so one pass handles both.
LIT verified live: over 300 random strings, Manacher’s answer has the same length as a brute-force longest palindrome, is itself a palindrome, and occurs in the string (window.__manacher). FIG no framing; exact.
A separator transform (inserting ‘#’ between characters) makes even- and odd-length palindromes uniform, so one pass handles both.
LIT verified live: over 300 random strings, Manacher’s answer has the same length as a brute-force longest palindrome, is itself a palindrome, and occurs in the string (window.__manacher). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at shared-memory — a palindrome’s two halves share a single centre, each the mirror of the other. Manacher’s reuse of the mirror radius is exactly memory shared across the fold. AVAN (AI) built the instrument: the separator transform, the mirror-reuse scan, the brute cross-check.
Credit as content: Glenn Manacher (1975). The weave: David names the shared centre; I let each new centre inherit its mirror’s radius and confirm the result matches an exhaustive search.
Credit as content: Glenn Manacher (1975). The weave: David names the shared centre; I let each new centre inherit its mirror’s radius and confirm the result matches an exhaustive search.
3 ONE DIMENSION
The transformed string with radii p[i]: each bar is how far the palindrome centred at position i reaches. The tallest bar is the longest palindrome; mirror positions inside a known palindrome copy their radius for free.
4 TWO DIMENSIONS · INTERACTIVE
Type or roll a string. Manacher highlights the longest palindromic substring; a brute-force search confirms the same length.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the longest palindrome, found in one linear pass.
AVAN’s addition (the inverse-companion): the naive re-expansion wastes work because palindromes share structure — a palindrome centred here already predicts a radius for its mirror position inside the current rightmost palindrome, so you never re-expand what symmetry guarantees. The inverse of ‘check every centre from scratch’ is ‘copy the mirror’s radius under the right boundary, and only expand past it.’ Reflection is the memory. Magenta is the redundant re-expansions skipped; green is the radii inherited from mirror centres. Symmetry pays for the linear time.
LIT Genuine Manacher's algorithm (Manacher 1975). Verified live: the linear-time mirror-reuse scan returns a substring whose length equals the brute-force longest palindrome, which is itself a palindrome and present in the string, for 300 random strings (window.__manacher.matchesBrute); 'abacabad' -> 'abacaba' (len 7).
FIG No framing: the separator transform, the mirror-reuse scan, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — a palindrome centered here predicts its mirror position's radius under the current right boundary, so redundant re-expansions are skipped; magenta is the skipped re-checks, green the inherited radii. Reflection is the memory that buys O(n).
FIG No framing: the separator transform, the mirror-reuse scan, and the brute cross-check run in-browser and agree exactly. The AVAN inverse is honest — a palindrome centered here predicts its mirror position's radius under the current right boundary, so redundant re-expansions are skipped; magenta is the skipped re-checks, green the inherited radii. Reflection is the memory that buys O(n).
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SHARED MEMORY · David Lee Wise (ROOT0), with AVAN