Pattern Guide
Palindrome Automaton (Eertree)
"Build all distinct palindromic substrings in O(n). Count occurrences in O(n)."
The palindrome automaton (Eertree) stores all distinct palindromic substrings of a string. It has at most n+2 nodes (one node per distinct palindrome, plus two root nodes). Builds incrementally in O(n) online. Each node represents a unique palindrome; suffix links connect to the longest proper palindromic suffix. Answers: count distinct palindromic substrings, count occurrences of each, solve string problems involving palindrome structure.
Problems you can solve with this pattern
3 problems · click any to start solving
class PalindromAutomaton {
constructor() {
// Node: {len, link, children, cnt}
this.nodes = [
{len: -1, link: 0, children: {}, cnt: 0}, // root -1
{len: 0, link: 0, children: {}, cnt: 0} // root 0 (empty palindrome)
];
this.last = 1; // last added palindrome's node index
this.s = '#'; // padding to handle index -1
}
getLink(v) {
// Traverse suffix links to find longest palindromic suffix that can be extended
while (this.s[this.s.length - 1 - this.nodes[v].len - 1] !== this.s[this.s.length - 1]) {
v = this.nodes[v].link;
}
return v;
}
extend(c) {
this.s += c;
let cur = this.getLink(this.last);
if (!this.nodes[cur].children[c]) {
const newNode = {len: this.nodes[cur].len + 2, children: {}, cnt: 1};
const link = this.nodes[cur].len === -1 ? 1 : this.nodes[this.getLink(this.nodes[cur].link)].children[c];
newNode.link = link || 1;
this.nodes.push(newNode);
this.nodes[cur].children[c] = this.nodes.length - 1;
} else {
this.nodes[this.nodes[cur].children[c]].cnt++;
}
this.last = this.nodes[cur].children[c];
return this.last;
}
// Propagate counts from children to suffix links (total occurrences)
build() {
for (let i = this.nodes.length - 1; i >= 2; i--) {
this.nodes[this.nodes[i].link].cnt += this.nodes[i].cnt;
}
}
countDistinct() { return this.nodes.length - 2; }
}Eertree has two root nodes: "-1 root" (imaginary palindrome of length -1, parent of all odd palindromes) and "0 root" (empty palindrome of length 0, parent of all even palindromes). Each node stores: length of palindrome, suffix link (longest proper palindromic suffix), and children (by extending character). Build online: for each new character s[i], find the longest palindromic suffix of s[0..i] that can be extended to include s[i].
class PalindromAutomaton {
constructor() {
// Node: {len, link, children, cnt}
this.nodes = [
{len: -1, link: 0, children: {}, cnt: 0}, // root -1
{len: 0, link: 0, children: {}, cnt: 0} // root 0 (empty palindrome)
];
this.last = 1; // last added palindrome's node index
this.s = '#'; // padding to handle index -1
}
getLink(v) {
// Traverse suffix links to find longest palindromic suffix that can be extended
while (this.s[this.s.length - 1 - this.nodes[v].len - 1] !== this.s[this.s.length - 1]) {
v = this.nodes[v].link;
}
return v;
}
extend(c) {
this.s += c;
let cur = this.getLink(this.last);
if (!this.nodes[cur].children[c]) {
const newNode = {len: this.nodes[cur].len + 2, children: {}, cnt: 1};
const link = this.nodes[cur].len === -1 ? 1 : this.nodes[this.getLink(this.nodes[cur].link)].children[c];
newNode.link = link || 1;
this.nodes.push(newNode);
this.nodes[cur].children[c] = this.nodes.length - 1;
} else {
this.nodes[this.nodes[cur].children[c]].cnt++;
}
this.last = this.nodes[cur].children[c];
return this.last;
}
// Propagate counts from children to suffix links (total occurrences)
build() {
for (let i = this.nodes.length - 1; i >= 2; i--) {
this.nodes[this.nodes[i].link].cnt += this.nodes[i].cnt;
}
}
countDistinct() { return this.nodes.length - 2; }
}- At most n+2 nodes for string of length n
- Each node = one distinct palindromic substring
- Suffix link of node P = longest proper palindromic suffix of P
- Build online in O(n) — each character extension is amortized O(1)
Key operations:
- Count distinct palindromic substrings: #nodes - 2
- Count occurrences: propagate cnt through suffix links
- Palindromic suffix decomposition: at each position, suffix links form the decomposition
vs Manacher's: Manacher's finds all palindrome radii but doesn't deduplicate or count occurrences. Eertree deduplicates but is more complex to implement.