Hi Codeforces!

During Codeforces Round 1059 (Div. 3), I encountered Problem E: Beautiful Palindromes, which involves minimizing palindromic subarrays. While researching optimal solutions, I discovered the Eertree (Palindromic Tree) data structure — a powerful but relatively unknown tool for efficiently handling palindrome-related problems.

The Eertree can process all palindromic substrings of a string in O(n) time and space, making it ideal for problems involving palindrome counting, queries, and optimizations. However, I noticed there are limited and scattered resources for learning this data structure, so I've compiled this comprehensive guide to help the community.

What is an Eertree (Palindromic Tree)?

The Palindromic Tree (also called Eertree) is a tree-like data structure that stores all unique palindromic substrings of a string efficiently. It was introduced by Mikhail Rubinchik and Arseny M. Shur in 2014.

Key Properties: - Processes strings in O(n) time complexity - Uses O(n) space (stores at most n+2 nodes) - Maintains two roots: one for odd-length palindromes (length -1) and one for even-length palindromes (length 0) - Uses suffix links similar to Aho-Corasick automaton - Can answer queries like: number of distinct palindromes, occurrences of each palindrome, longest palindromic suffix, etc.

When to use Eertree vs Manacher's Algorithm:

• Manacher's: Finding all palindromic substrings, longest palindromic substring (simpler implementation)

• Eertree: Counting distinct palindromes, palindrome occurrences, dynamic palindrome queries, complex palindrome properties.

Core Resources

Original Research Paper

• EERTREE: An Efficient Data Structure for Processing Palindromes in Strings
  Authors: Mikhail Rubinchik, Arseny M. Shur (2015)
  arXiv: Paper on Eertree
  This is the foundational paper explaining the theory and proofs.

Codeforces Tutorials

1. Palindromic Tree Introduction by droptable
   https://codeforces.me/blog/entry/13958
   Excellent beginner-friendly tutorial with implementation details and example problems.

2. A Bit More About Palindromes by adamant
   https://codeforces.me/blog/entry/19193
   Advanced applications including palindrome factorization and Rich words.

3. Double-ended Eertree
   https://codeforces.me/blog/entry/130276
   Extension for processing palindromes when adding characters to both ends.

C++ Implementations:

• GitHub Topic: Palindromic Tree
  https://github.com/topics/palindromic-tree
  Multiple implementations in different languages.

• Sotanishy's CP Library
  Palindromic Tree

• My Personal Implementation : Palindromic Tree
  github.com/Muszic/Algorithms

Java Implementations:

• Alessiop86's Eertree https://github.com/alessiop86/eertree

Other Tutorials

• GeeksforGeeks: Palindromic Tree Introduction & Implementation
  https://www.geeksforgeeks.org/dsa/palindromic-tree-introduction-implementation/
  Step-by-step explanation with visual examples.

• Scribd.com: Eertree: An Efficient Data Structure For Processing Palindromes in Strings https://www.scribd.com/document/641773961/Untitled

• OpenGenus IQ — Palindromic Tree (Eertree) https://iq.opengenus.org/palindromic-tree-eertree/

• E.Choroba's Blog — Eertree Implementation Eertree: Palindromic Tree

Practice Problems

Here are some problems where Eertree can be applied:

Beginner:

1. SPOJ — NUMOFPAL: Count number of palindromic substrings
   http://www.spoj.com/problems/NUMOFPAL/

2. Eertree Library Checker

3. Longest Palindrome CSES

4. Palindromes and Super Abilities VJudge

5. Palindromes and Super Abilities 2 VJudge

6. SPOJ — LPS: Longest Palindromic Substring
   http://www.spoj.com/problems/LPS/

Intermediate:

1. Codeforces Round 1059 (Div. 3) — Problem E: Beautiful Palindromes
   https://codeforces.me/contest/2059/problem/E
   The problem that inspired this blog!

2. HDU-3948: The Number of Palindromes
   VJudge

3. Codeforces-Palisection https://codeforces.me/contest/17/problem/E

4. Virus synthesis Codeforces GYM

5. The Problem to Slow Down You Codeforces GYM

Advanced:

1. 100500 palidnromes VJudge

2. Palindromadness Codeforces GYM

3. Problems involving palindrome factorization

4. Dynamic palindrome queries with updates
5. Palindrome automaton constructions

Why This Matters

The Eertree is an elegant solution to many palindrome problems that would otherwise require complex DP or heavy preprocessing. It's especially useful in competitive programming when: - You need to count distinct palindromes efficiently - You need to track palindrome properties dynamically - Standard approaches like Manacher's don't provide enough information

Conclusion

I hope this collection of resources helps you master the Eertree data structure! It's a powerful tool that deserves more attention in the competitive programming community. Feel free to ask questions in the comments, and happy coding!

Special thanks to droptable, adamant, and the original authors Rubinchik and Shur for their contributions to this topic.