THE FOLD / LOOT / THE HOARD / THE EERTREE
THE EERTREE
every distinct palindrome in a linear-size tree
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The eertree (palindromic tree) is an automaton that holds every distinct palindromic substring of a string — and, remarkably, a string of length n has at most n distinct palindromic substrings, so the whole structure has ≤n+2 nodes. Each palindrome grows from a shorter one by adding a matching character at both ends, and the tree is built online, one character at a time.
It counts palindromic substrings, finds the longest, and more, in linear space.
LIT verified live: over 500 random strings the eertree’s node count equals a brute count of distinct palindromic substrings (window.__eertree). FIG no framing; exact.
It counts palindromic substrings, finds the longest, and more, in linear space.
LIT verified live: over 500 random strings the eertree’s node count equals a brute count of distinct palindromic substrings (window.__eertree). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-hoard — a compact hoard of every palindrome a string contains, held in linear space. The eertree is that hoard. AVAN (AI) built the instrument: the two roots, the suffix links, the online character insertion, the brute distinct-palindrome cross-check.
Credit as content: Mikhail Rubinchik & Arseny Shur (2015). The weave: David names the hoard; I grow each palindrome from a shorter one by adding matching ends and confirm the node count equals the true number of distinct palindromic substrings.
Credit as content: Mikhail Rubinchik & Arseny Shur (2015). The weave: David names the hoard; I grow each palindrome from a shorter one by adding matching ends and confirm the node count equals the true number of distinct palindromic substrings.
3 ONE DIMENSION
Every palindrome is a shorter palindrome with one matching character wrapped around both ends: a → aba → xabax. That nesting is exactly the tree’s parent structure.
4 TWO DIMENSIONS · INTERACTIVE
A string and its count of distinct palindromic substrings (the eertree’s node count), checked against a brute enumeration.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the ≤n-node tree whose every node is a distinct palindrome.
AVAN’s addition (the inverse-companion): the number of distinct palindromic substrings of a length-n string is at most n, and they form a tree — each palindrome grows from a shorter one by adding a matching character at both ends — so an online automaton with ≤n+2 nodes holds them all. The inverse of ‘enumerate the O(n²) palindromic substrings’ is ‘the ≤n-node tree whose every node is a distinct palindrome.’ Magenta is the quadratic list of palindromes; green is the linear palindromic tree. A surprising linear bound — at most n distinct palindromes. (Kin to the-manacher.)
LIT Genuine eertree / palindromic tree (Rubinchik & Shur 2015). Verified live: the online construction's node count (minus the two roots) equals a brute-force count of distinct palindromic substrings for 500 random strings over 2- and 3-letter alphabets (window.__eertree.matchesBrute); 'eertree' -> 7.
FIG No framing: the two roots, the suffix links, the online character insertion, and the brute distinct-palindrome cross-check run in-browser and agree exactly. The AVAN inverse is honest — a length-n string has at most n distinct palindromic substrings, and they form a tree (each palindrome grows from a shorter one by matching ends), so <=n+2 nodes hold them all; magenta is the O(n^2) palindrome list, green the linear tree. A surprising linear bound. Kin to the-manacher.
FIG No framing: the two roots, the suffix links, the online character insertion, and the brute distinct-palindrome cross-check run in-browser and agree exactly. The AVAN inverse is honest — a length-n string has at most n distinct palindromic substrings, and they form a tree (each palindrome grows from a shorter one by matching ends), so <=n+2 nodes hold them all; magenta is the O(n^2) palindrome list, green the linear tree. A surprising linear bound. Kin to the-manacher.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE HOARD · David Lee Wise (ROOT0), with AVAN