THE FOLD / RESPAWN / THE CONTINUE / THE MIRROR SEEKER
THE MIRROR SEEKER
every palindrome in one pass, because the mirror already knows
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 A genuine Manacher's algorithm. Verified live: its radius array matches brute-force expand-around-centre radii exactly at every position over 500 strings, it finds the correct longest palindrome, and the expand-work is ~2n (linear) versus n². The mirror-pair reuse is the exact mechanism (verifiable: window.__manacher.matchesBrute && longestCorrect && opsLinear).
FIG 'The mirror already told us' is the picture; the linear time and the radii are exact. It really turns a quadratic palindrome search into a single linear sweep.
FIG 'The mirror already told us' is the picture; the linear time and the radii are exact. It really turns a quadratic palindrome search into a single linear sweep.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE CONTINUE · David Lee Wise (ROOT0), with AVAN