The Palindromic Tree

A palindrome is a string that reads the same forwards and backwards: racecar, level, abba. Finding one is easy. Counting all distinct palindromic substrings in a long piece of text — without duplicates — turns out to be surprisingly subtle.

A string of length $n$ can have up to $n$ distinct palindromic substrings (one ending at each position, a result known since the early 2000s). Naively checking every substring is $O(n^2)$ at best; storing them all without a compact representation wastes enormous space.

In 2013–2015, Mikhail Rubinchik and Arseny M. Shur introduced the eertree (also called the palindromic tree): a single data structure that represents every distinct palindromic substring of a text, built online — one character at a time — in $O(n)$ time and $O(n)$ space. The name is a portmanteau of eertree because the structure looks like a tree and "eert" is "tree" backwards — a nod to its palindromic soul.

Type any string into the box below. The demo builds the eertree character by character and lists every distinct palindromic substring it finds — including the trivial single characters.

<p class="hint">{{hint}}</p>
<div class="input-row">
  <input id="txt" type="text" maxlength="40" placeholder="{{placeholder}}" autocomplete="off" spellcheck="false" />
  <button id="clear" type="button" class="ghost">{{btn_clear}}</button>
</div>
<div class="status-row">
  <span class="label">{{label_count}}</span>
  <span id="count" class="count">0</span>
</div>
<div id="pal-list" class="pal-list"></div>
<div class="brute-row">
  <button id="brute" type="button">{{btn_brute}}</button>
  <span id="brute-msg" class="brute-msg"></span>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.input-row { display: flex; gap: .5rem; margin-bottom: .7rem; }
#txt { flex: 1; font: 600 16px ui-monospace, monospace; padding: .45rem .7rem;
       border: 1px solid #adb1b8; border-radius: 8px; outline: none; }
#txt:focus { border-color: #1d3557; box-shadow: 0 0 0 2px #1d355722; }
.status-row { display: flex; align-items: baseline; gap: .5rem; margin-bottom: .5rem; }
.label { font-size: .9rem; color: #555; }
.count { font: 700 1.6rem ui-monospace, monospace; color: #1d3557; min-width: 2.5rem; }
.pal-list { display: flex; flex-wrap: wrap; gap: .35rem; min-height: 2.2rem; margin-bottom: .9rem; }
.pal-chip { background: #e8eef3; border: 1px solid #cdd9e3; color: #1d3557;
            font: 600 13px ui-monospace, monospace; padding: .2rem .55rem; border-radius: 20px; }
.pal-chip.new { background: #d0f0e0; border-color: #4caf88; color: #0a5c34; animation: pop .25s ease; }
@keyframes pop { 0%{transform:scale(.7);opacity:0} 100%{transform:scale(1);opacity:1} }
.brute-row { display: flex; align-items: center; gap: .7rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.brute-msg { font-size: .9rem; color: #444; }
.brute-msg.ok { color: #0a7d33; font-weight: 600; }
.brute-msg.bad { color: #c92f3c; font-weight: 600; }

// Code not found

Notice how the count of distinct palindromes grows at most by one per character added. That is not a coincidence — it is the core theorem that makes the eertree work. Each new character can introduce at most one new palindromic suffix not seen before, so the tree stays linear in size no matter how long the text grows.

Compare this with the brute-force approach: for a string of length $n$ there are $O(n^2)$ substrings to check, and checking each one for palindromicity takes $O(n)$ time — a total of $O(n^3)$ without clever tricks. The eertree does the whole job in $O(n)$.

The eertree's guarantees are provably tight. Here is what is known:

• At most $n$ distinct palindromic substrings. Every string of length $n$ has at most $n$ distinct palindromic substrings (plus the two imaginary roots). This was proven by Droubay, Justin, and Pirillo in 2001, and it is what makes a linear-size catalogue possible.
• $O(n)$ construction (proven, 2015). Rubinchik and Shur proved in their 2015 paper that each character appended to the string requires only $O(1)$ amortized work — the suffix-link pointer always allows the algorithm to find the longest palindromic suffix of the current prefix without re-scanning. Total construction: $O(n)$ time, $O(n)$ space.
• $O(n \log |\Sigma|)$ with a hash map. The standard implementation stores children in a hash map; with a sorted array or trie-like structure the per-node cost can rise to $O(\log |\Sigma|)$, where $\Sigma$ is the alphabet. For a fixed alphabet (e.g. DNA's four bases) the constant is negligible.
• Online algorithm. Unlike suffix arrays, the eertree processes the string one character at a time and maintains a fully correct catalogue at every prefix. This is essential for streaming applications.

The eertree does not solve an NP-hard problem — it is firmly in the polynomial, even linear, world. But it is an impressive example of how the right data structure can compress what looks like quadratic work into a single linear pass, placing it in the same family of linear-time string tools as the suffix array and Aho-Corasick automaton. For related hardness results in string problems, see P vs NP.

Palindromic substrings appear in surprisingly many domains:

• Genomics and bioinformatics: DNA palindromes (sequences equal to their reverse complement) are recognition sites for restriction enzymes. Cataloguing all such sites in a genome quickly is a direct application of eertree-style algorithms.
• Data compression: some compression schemes exploit repeated palindromic patterns. An eertree can expose the full palindromic structure of a block of data in linear time.
• Natural-language processing: detecting repeated mirrored patterns in text — useful in poetry analysis, stylometry, and anomaly detection — benefits from the complete palindrome catalogue the eertree provides.
• Competitive programming: the eertree has become a standard weapon in algorithmic competitions for problems that ask "how many distinct palindromic substrings does this string have?" or "what is the palindromic factorization?"
• Palindromic factorization: every string can be written as a concatenation of palindromes. The eertree underlies the fastest known algorithms for finding the minimum such factorization, running in $O(n \log n)$ time.

The eertree is a beautiful example of how a careful observation — at most one new palindromic suffix per character — can reduce a seemingly hard enumeration problem to a single linear scan, echoing the efficiency gains seen in pattern matching algorithms.

The eertree is one of those rare data structures that feels almost magical: one character at a time, without ever looking back, it assembles a complete catalogue of every distinct palindrome hiding inside a string. The key insight — that each new character introduces at most one new palindromic suffix — turns what looks like a quadratic enumeration into a single linear pass.

Introduced by Rubinchik and Shur in 2015, the eertree is provably optimal: the catalogue has at most $n$ entries, and it is built in $O(n)$ time. That places it alongside the suffix array and Aho-Corasick automaton as a fundamental linear-time string tool — and it is young enough that new applications are still being discovered.

Next time you spot a palindrome in a genome, a poem, or a competition problem, remember: there is a linear-time tree that has already found all of them. For more on the difficulty of string and search problems, explore pattern matching and P vs NP.