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. To find the longest palindrome in a string, the naive way tries every centre and expands outward — O(n²). Manacher does it in one linear pass with a mirror trick: whenever you’re inside a palindrome you already found, the radius at a position is at least the radius at its mirror position (already computed), so you never re-check that part. It hands you the palindrome radius at every centre in O(n).
LIT verified: Manacher’s radius array matches the brute-force expand-around-centre radii exactly at every position, it finds the correct longest palindrome, and the expand-work is ~2n (linear), not n². FIG ‘the mirror already told us’ is the picture; the linear time and the radii are exact.
LIT verified: Manacher’s radius array matches the brute-force expand-around-centre radii exactly at every position, it finds the correct longest palindrome, and the expand-work is ~2n (linear), not n². FIG ‘the mirror already told us’ is the picture; the linear time and the radii are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) brought the thread — the corpus runs string machinery and symmetry (THE SHORTEST WITNESS’s sequences, the word combinatorics) and the idea that the fastest algorithms are the ones that never redo work. AVAN (AI) built this instrument: the linear sweep, the radius mountain-range, and the mirror-pair links.
The weave: David names the mirror seeker and its seat at THE CONTINUE (continue from the mirror instead of restarting); I make the radius profile a strip in 1D, the sweep live in 2D, and the symmetric ridge with its mirror arcs in 3D. The sphere is the seam.
The weave: David names the mirror seeker and its seat at THE CONTINUE (continue from the mirror instead of restarting); I make the radius profile a strip in 1D, the sweep live in 2D, and the symmetric ridge with its mirror arcs in 3D. The sphere is the seam.
3 ONE DIMENSION
The palindrome-radius profile: over each centre, a peak whose height is how far the palindrome reaches. The tallest peak marks the longest palindrome, underlined in the string below. One symmetric mountain range, read in a single sweep.
4 TWO DIMENSIONS · INTERACTIVE
Pick a string and watch Manacher work: the radius at every centre, the longest palindrome lit up, and the op-count — linear, a fraction of the brute-force n². The mirror shortcut is doing the saving.
5 THREE DIMENSIONS + AVAN’S INVERSE
The radius ridge in space, turning — a symmetric mountain range whose highest summit is the answer. Green is the profile Manacher computes left to right.
AVAN’s addition (the inverse-companion): the magenta arcs link each centre to its mirror inside the current palindrome — the reflections whose radii are simply copied, never recomputed. That mirror map is the algorithm: every peak on the right is the reflection of one on the left, so the whole ridge is symmetric, and the work is halved by looking backward. The seeker is the mirror.
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