Introduction

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 nn can have up to nn distinct palindromic substrings (one ending at each position, a result known since the early 2000s). Naively checking every substring is O(n2)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)O(n) time and O(n)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.

Try It

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">Type a string below. The eertree is built character by character — each step can add <b>at most one</b> new distinct palindromic substring. Watch the count and the list update in real time.</p>
<div class="input-row">
  <input id="txt" type="text" maxlength="40" placeholder="e.g. abaab" autocomplete="off" spellcheck="false" />
  <button id="clear" type="button" class="ghost">Clear</button>
</div>
<div class="status-row">
  <span class="label">Distinct palindromic substrings:</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">Verify with brute force</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Eertree (Palindromic Tree) implementation.
// Two imaginary roots: root_odd (length -1) and root_even (length 0).
// Each node stores: len, suffLink, children (map char->node).
// Core invariant: after processing s[0..i], `last` points to the node
// Adding s[i]: walk up via suffLink until s[i - node.len - 1] == s[i],

function buildEertree(s) {
  const nodes = [];
  function newNode(len, suffLink) {
    nodes.push({ len, suffLink, children: {}, label: null });
    return nodes.length - 1;
  }
  const ROOT_ODD  = newNode(-1, 0); // imaginary root with length -1
  const ROOT_EVEN = newNode( 0, ROOT_ODD); // imaginary root with length 0
  let last = ROOT_EVEN;
  const newPalindromes = []; // list of {step, label} for newly added nodes

  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    // Find the longest palindromic suffix of s[0..i-1] such that
    // s[i - len - 1] == s[i] (so we can extend it on both sides).
    let cur = last;
    while (true) {
      const j = i - nodes[cur].len - 1;
      if (j >= 0 && s[j] === c) break;
      cur = nodes[cur].suffLink;
    }
    if (nodes[cur].children[c] !== undefined) {
      last = nodes[cur].children[c];
    } else {
      // Create a new node: its length is nodes[cur].len + 2
      const newLen = nodes[cur].len + 2;
      const newIdx = newNode(newLen, -1); // suffLink to be determined
      nodes[cur].children[c] = newIdx;
      // Determine suffix link for the new node
      if (newLen === 1) {
        nodes[newIdx].suffLink = ROOT_EVEN;
      } else {
        let tmp = nodes[cur].suffLink;
        while (true) {
          const j = i - nodes[tmp].len - 1;
          if (j >= 0 && s[j] === c) break;
          tmp = nodes[tmp].suffLink;
        }
        nodes[newIdx].suffLink = nodes[tmp].children[c] !== undefined
          ? nodes[tmp].children[c]
          : ROOT_EVEN;
      }
      // Recover the actual palindrome label
      const halfLen = Math.floor(newLen / 2);
      const startIdx = i - newLen + 1;
      nodes[newIdx].label = s.slice(startIdx, startIdx + newLen);
      newPalindromes.push({ step: i, label: nodes[newIdx].label });
      last = newIdx;
    }
  }
  // Collect all distinct palindromes (real nodes only, excluding the two imaginary roots)
  const all = nodes.slice(2).filter(n => n.label !== null).map(n => n.label);
  return { all, newPalindromes };
}

// Brute-force: collect all distinct palindromic substrings by checking every substring.
function bruteForcePalindromes(s) {
  const set = new Set();
  for (let i = 0; i < s.length; i++) {
    for (let j = i + 1; j <= s.length; j++) {
      const sub = s.slice(i, j);
      const rev = sub.split('').reverse().join('');
      if (sub === rev) set.add(sub);
    }
  }
  return [...set].sort((a, b) => a.length - b.length || a.localeCompare(b));
}

let prevLabels = new Set();

function update() {
  const s = document.getElementById('txt').value;
  const list = document.getElementById('pal-list');
  const countEl = document.getElementById('count');
  const bruteMsg = document.getElementById('brute-msg');
  bruteMsg.textContent = '';
  bruteMsg.className = 'brute-msg';

  if (!s) {
    list.innerHTML = '';
    countEl.textContent = '0';
    prevLabels = new Set();
    return;
  }

  const { all } = buildEertree(s);
  const sorted = [...all].sort((a, b) => a.length - b.length || a.localeCompare(b));
  const newSet = new Set(all);

  list.innerHTML = '';
  sorted.forEach(p => {
    const chip = document.createElement('span');
    chip.className = 'pal-chip' + (!prevLabels.has(p) ? ' new' : '');
    chip.textContent = p;
    list.appendChild(chip);
  });
  countEl.textContent = sorted.length;
  prevLabels = newSet;
}

document.getElementById('txt').addEventListener('input', update);
document.getElementById('clear').addEventListener('click', () => {
  document.getElementById('txt').value = '';
  update();
});
document.getElementById('brute').addEventListener('click', () => {
  const s = document.getElementById('txt').value;
  const msg = document.getElementById('brute-msg');
  if (!s) { msg.textContent = 'Enter a string first.'; msg.className = 'brute-msg'; return; }
  const { all: eertreeAll } = buildEertree(s);
  const brute = bruteForcePalindromes(s);
  const eertreeSet = new Set(eertreeAll);
  const bruteSet = new Set(brute);
  const match = eertreeAll.length === brute.length &&
                brute.every(p => eertreeSet.has(p));
  if (match) {
    msg.textContent = fmt('✓ Eertree and brute force agree: %length% distinct palindrome(s).', { length: brute.length });
    msg.className = 'brute-msg ok';
  } else {
    msg.textContent = fmt('✗ Mismatch! Eertree: %length%, brute force: %length2%', { length: eertreeAll.length, length2: brute.length });
    msg.className = 'brute-msg bad';
  }
});

// Pre-load with a nice example
document.getElementById('txt').value = 'abaab';
update();
Result
Console

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 nn there are O(n2)O(n^2) substrings to check, and checking each one for palindromicity takes O(n)O(n) time — a total of O(n3)O(n^3) without clever tricks. The eertree does the whole job in O(n)O(n).

The Real Complexity

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

  • At most nn distinct palindromic substrings. Every string of length nn has at most nn 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)O(n) construction (proven, 2015). Rubinchik and Shur proved in their 2015 paper that each character appended to the string requires only O(1)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)O(n) time, O(n)O(n) space.
  • O(nlog⁡∣Σ∣)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⁡∣Σ∣)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.

Where It Matters

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(nlog⁡n)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.

Conclusion

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 nn entries, and it is built in O(n)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/eertree/Content licensed under CC BY-NC 4.0.