Palindromic Tree (Eertree)

A palindromic tree, or eertree, stores each distinct nonempty palindromic substring of a text as one node. Unlike Manacher’s algorithm, which describes palindrome radii at centers, an eertree directly identifies distinct palindrome values and links each to its longest proper palindromic suffix. It supports online processing: append a character, discover whether a new palindrome appears, and update the longest palindromic suffix. A length-n string has at most n distinct nonempty palindromes, making the structure surprisingly compact. This lesson constructs a fixed-lowercase eertree, counts its palindrome nodes, finds the longest palindrome length, and prints the longest palindromic suffix after each append.

Prerequisites: Palindromes, string indices, tries, suffix links or failure links, amortized analysis.

Build the idea

1. 1. Edges wrap a palindrome

   If a node represents palindrome P, a transition labeled c represents cPc. For example, a transition labeled b from a represents bab. This is not a trie edge that simply appends a character: the new character occurs on both sides. Odd and even palindromes need different starting points. Use two artificial roots: node 0 has length -1, and node 1 has length 0 for the empty palindrome. A c-edge from the -1 root creates the single letter c; a c-edge from the empty root creates cc. Artificial roots are not counted as nonempty palindromes.

2. 2. Suffix links and the current suffix

   Every real node has a link to its longest proper palindromic suffix. For ababa, the link chain is ababa→aba→a→empty. These links let us consider candidate palindromes in decreasing length without scanning every substring. last identifies the longest palindromic suffix of the processed prefix. Before any characters, last is the empty root. The -1 root links to itself; the empty root links to the -1 root. These special choices make the same extension search work for the first character and for even-length palindromes.

3. 3. Find a suffix that can be wrapped

   Appending s[pos]=c can extend a previous palindromic suffix P when the character just before its occurrence equals c. Its index is pos-1-len[P]. Check that this index is nonnegative before accessing the string. Starting at last, follow suffix links until the check succeeds. The -1 root guarantees success because its computed index is pos, the newly appended character itself. For a length-zero candidate, the check compares c with the previous character, naturally detecting a palindrome of length two.

4. 4. Create at most one new palindrome

   After finding candidate P, follow its c-transition if it already exists; this is the new last. Otherwise create node cPc with length len[P]+2. Only the longest palindromic suffix can be new: any shorter palindromic suffix also occurs as a prefix of this longer palindrome, ending before the newly appended position, so it was already present. Thus an append creates at most one real node. For a one-letter node, its suffix link is the empty root. For longer nodes, repeat the extension search from link[P], then follow that candidate's c-transition to obtain the correct proper palindromic suffix.

5. 5. Trace odd and even examples

   Process ababa. Successive longest palindromic suffixes are a,b,aba,bab,ababa, with lengths [1,1,3,3,5]. The five distinct palindrome values are a,b,aba,bab,ababa. After reading ab and appending a, the previous longest suffix b is preceded by a, so wrapping creates aba and its suffix link goes to a. Now process aa separately: the first a is created from the -1 root; the second a can wrap the empty root, creating aa with link to a. This demonstrates why a single artificial root cannot conveniently represent both parity cases.

6. 6. Understand counts and occurrence information

   The number of distinct palindromes equals nodeCount-2. The maximum real-node length is the longest palindrome length. Neither quantity counts occurrences: in aaaa there are four distinct palindromes but ten palindromic substring occurrences. To add occurrence counts, increase only the current last node at each position, then propagate counts from longer nodes to their suffix links in decreasing length order. The program intentionally does not conflate this extension with its distinct-node count. Returning to an existing node on append does not increase the number of distinct palindromes.

7. 7. Correctness, efficiency, and limits

   The longest suffix before append and its suffix-link chain enumerate all possible previous palindromic suffixes. The first extendable candidate is the longest new suffix, because wrapping preserves their length order. Existing transitions identify identical palindrome values; a newly created transition is therefore genuinely new. Across an append-only construction, suffix-link scans have linear aggregate work for a fixed alphabet, although one append can scan many links. Adding deletions would invalidate that amortized claim without extra machinery. Integer node indices are kept across vector growth, and no stale references survive allocation. Empty input leaves only the two roots and an empty suffix-length sequence.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<string>
#include<vector>
#include<array>
#include<algorithm>
using namespace std;
struct Node{
    int len=0,link=0;
    array<int,26>next{};
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    getline(cin,s);
    vector<Node>t(2);
    t[0].len=-1;
    t[0].link=0;
    t[1].len=0;
    t[1].link=0;
    int last=1,longest=0;
    vector<int>suffixLengths;
    // Find the longest suffix whose occurrence can be wrapped by s[pos].
    auto extendable=[&](int v,int pos){
        while(true){
            int before=pos-1-t[v].len;
            if(before>=0&&s[before]==s[pos]){
                return v;
            }
            v=t[v].link;
        }
    };
    for(int pos=0;pos<(int)s.size();pos++){
        int c=s[pos]-'a',p=extendable(last,pos);
        if(t[p].next[c]==0){
            Node node;
            node.len=t[p].len+2;
            if(node.len==1){
                node.link=1; // Single letter -> empty palindrome.
            }
            else{
                int q=extendable(t[p].link,pos);
                node.link=t[q].next[c]; // Proper suffix already exists.
            }
            int id=(int)t.size();
            t.push_back(node);
            t[p].next[c]=id; // Use indices safely after vector growth.
        }
        last=t[p].next[c];
        suffixLengths.push_back(t[last].len);
        longest=max(longest,t[last].len);
    }
    cout<<t.size()-2<<'\n'<<longest<<'\n';
    for(int i=0;i<(int)suffixLengths.size();i++){
        if(i){
            cout<<' ';
        }
        cout<<suffixLengths[i];
    }
    cout<<'\n'; // Empty input still prints the third, blank line.
}

Complexity analysis

For the fixed 26-letter alphabet, append-only construction takes O(n) amortized total time, with at most n+2 nodes and at most n actual wrapping edges. Dense child arrays use O(26n)=O(n) space. One append may take O(n) time; it is not worst-case constant. General balanced-map transitions give O(n log σ) total construction for alphabet size σ.

Example input and output

One line containing lowercase a–z text, possibly empty, length≤200000. Print distinct nonempty palindrome count on line 1, longest palindrome length on line 2, and longest palindromic-suffix length for each processed prefix on line 3. Empty input prints 0, 0, then a blank line.

Input

ababa

Output

5
5
1 1 3 3 5

The distinct palindromes are a,b,aba,bab,ababa. Each prefix has longest palindromic suffix length 1,1,3,3,5 respectively.

Practical applications

Distinct palindrome counting online; longest palindromic suffix after each append; occurrence aggregation; palindrome-factorization DP with additional optimizations. Original reference: Rubinchik and Shur, EERTREE: An Efficient Data Structure for Processing Palindromes in Strings.

Check your understanding

What does a transition labeled c from palindrome P represent?

Put it into practice

Add a count of every palindrome’s total occurrences, including overlapping ones.