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 ](https://arxiv.org/abs/1506.04862) ↵
This is the foundational paper explaining the theory and proofs.↵
↵
#### Codeforces Tutorials↵
↵
1. **Palindromic Tree Introduction** by droptable ↵
[https://codeforces.me/blog/entry/13958](https://web.archive.org/web/20160826200104/http://adilet.org/blog/25-09-14/) ↵
Excellent beginner-friendly tutorial with implementation details and example problems.↵
↵
2. **A Bit More About Palindromes** by adamant ↵
[https://codeforces.me/blog/entry/19193](https://codeforces.me/blog/entry/19193) ↵
Advanced applications including palindrome factorization and Rich words.↵
↵
3. **Double-ended Eertree** ↵
[https://codeforces.me/blog/entry/130276](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](https://github.com/topics/palindromic-tree) ↵
Multiple implementations in different languages.↵
↵
- **Sotanishy's CP Library**<br>↵
[Palindromic Tree](https://sotanishy.github.io/cp-library-cpp/string/palindromic_tree.hpp.html)↵
↵
- **My Personal Implementation : Palindromic Tree**<br>↵
[github.com/Muszic/Algorithms](https://github.com/Muszic/Algorithms/blob/main/Palindromic%20Tree.cpp)↵
↵
## Java Implementations:↵
- **Alessiop86's Eertree** ↵
[https://github.com/alessiop86/eertree](https://github.com/alessiop86/eertree)↵
↵
↵
↵
#### Other Tutorials↵
↵
- **GeeksforGeeks: Palindromic Tree Introduction & Implementation** ↵
[https://www.geeksforgeeks.org/dsa/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](https://www.scribd.com/document/641773961/Untitled) ↵
↵
- **OpenGenus IQ — Palindromic Tree (Eertree)**↵
[https://iq.opengenus.org/palindromic-tree-eertree/](https://iq.opengenus.org/palindromic-tree-eertree/) ↵
↵
- **E.Choroba's Blog — Eertree Implementation**↵
[Eertree: Palindromic Tree](https://blogs.perl.org/users/e_choroba/2022/01/eertree-palindromic-tree.html)↵
↵
↵
### 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/](http://www.spoj.com/problems/NUMOFPAL/)↵
↵
2. **Eertree** ↵
[Library Checker](https://judge.yosupo.jp/problem/eertree)↵
↵
3. **Longest Palindrome**↵
[CSES](https://cses.fi/problemset/task/1111)↵
↵
4. **Palindromes and Super Abilities**↵
[VJudge](https://acm.timus.ru/problem.aspx?space=1&num=1960)↵
↵
5. **Palindromes and Super Abilities 2**↵
[VJudge](https://acm.timus.ru/problem.aspx?space=1&num=2040)↵
↵
6. **SPOJ — LPS**: Longest Palindromic Substring ↵
[http://www.spoj.com/problems/LPS/](http://www.spoj.com/problems/LPS/)↵
↵
**Intermediate:**↵
↵
1. **Codeforces Round 1059 (Div. 3) — Problem E: Beautiful Palindromes** ↵
[https://codeforces.me/contest/2059/problem/E](https://codeforces.me/contest/2162/problem/E) ↵
The problem that inspired this blog!↵
↵
2. **HDU-3948**: The Number of Palindromes ↵
[VJudge](https://vjudge.net/problem/HDU-3948)↵
↵
3. **Codeforces-Palisection**↵
[https://codeforces.me/contest/17/problem/E](https://codeforces.me/contest/17/problem/E)↵
↵
4. **Virus synthesis**↵
[Codeforces GYM](https://codeforces.me/gym/100548/attachments)↵
↵
5. **The Problem to Slow Down You**↵
[Codeforces GYM](https://codeforces.me/gym/100548/attachments)↵
↵
**Advanced:**↵
↵
1. **100500 palidnromes**↵
[VJudge](https://acm.timus.ru/problem.aspx?space=1&num=2058)↵
↵
2. **Palindromadness**↵
[Codeforces GYM](https://codeforces.me/gym/102141/attachments)↵
↵
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.↵
↵
↵
↵
[cut]↵
↵
Comprehensive resource guide for Eertree (Palindromic Tree) data structure, inspired by Problem E from Codeforces Round 1059 (Div. 3). Includes tutorials, implementations, and practice problems.↵
↵
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 ](https://arxiv.org/abs/1506.04862) ↵
This is the foundational paper explaining the theory and proofs.↵
↵
#### Codeforces Tutorials↵
↵
1. **Palindromic Tree Introduction** by droptable ↵
[https://codeforces.me/blog/entry/13958](https://web.archive.org/web/20160826200104/http://adilet.org/blog/25-09-14/) ↵
Excellent beginner-friendly tutorial with implementation details and example problems.↵
↵
2. **A Bit More About Palindromes** by adamant ↵
[https://codeforces.me/blog/entry/19193](https://codeforces.me/blog/entry/19193) ↵
Advanced applications including palindrome factorization and Rich words.↵
↵
3. **Double-ended Eertree** ↵
[https://codeforces.me/blog/entry/130276](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](https://github.com/topics/palindromic-tree) ↵
Multiple implementations in different languages.↵
↵
- **Sotanishy's CP Library**<br>↵
[Palindromic Tree](https://sotanishy.github.io/cp-library-cpp/string/palindromic_tree.hpp.html)↵
↵
- **My Personal Implementation : Palindromic Tree**<br>↵
[github.com/Muszic/Algorithms](https://github.com/Muszic/Algorithms/blob/main/Palindromic%20Tree.cpp)↵
↵
## Java Implementations:↵
- **Alessiop86's Eertree** ↵
[https://github.com/alessiop86/eertree](https://github.com/alessiop86/eertree)↵
↵
↵
↵
#### Other Tutorials↵
↵
- **GeeksforGeeks: Palindromic Tree Introduction & Implementation** ↵
[https://www.geeksforgeeks.org/dsa/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](https://www.scribd.com/document/641773961/Untitled) ↵
↵
- **OpenGenus IQ — Palindromic Tree (Eertree)**↵
[https://iq.opengenus.org/palindromic-tree-eertree/](https://iq.opengenus.org/palindromic-tree-eertree/) ↵
↵
- **E.Choroba's Blog — Eertree Implementation**↵
[Eertree: Palindromic Tree](https://blogs.perl.org/users/e_choroba/2022/01/eertree-palindromic-tree.html)↵
↵
↵
### 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/](http://www.spoj.com/problems/NUMOFPAL/)↵
↵
2. **Eertree** ↵
[Library Checker](https://judge.yosupo.jp/problem/eertree)↵
↵
3. **Longest Palindrome**↵
[CSES](https://cses.fi/problemset/task/1111)↵
↵
4. **Palindromes and Super Abilities**↵
[VJudge](https://acm.timus.ru/problem.aspx?space=1&num=1960)↵
↵
5. **Palindromes and Super Abilities 2**↵
[VJudge](https://acm.timus.ru/problem.aspx?space=1&num=2040)↵
↵
6. **SPOJ — LPS**: Longest Palindromic Substring ↵
[http://www.spoj.com/problems/LPS/](http://www.spoj.com/problems/LPS/)↵
↵
**Intermediate:**↵
↵
1. **Codeforces Round 1059 (Div. 3) — Problem E: Beautiful Palindromes** ↵
[https://codeforces.me/contest/2059/problem/E](https://codeforces.me/contest/2162/problem/E) ↵
The problem that inspired this blog!↵
↵
2. **HDU-3948**: The Number of Palindromes ↵
[VJudge](https://vjudge.net/problem/HDU-3948)↵
↵
3. **Codeforces-Palisection**↵
[https://codeforces.me/contest/17/problem/E](https://codeforces.me/contest/17/problem/E)↵
↵
4. **Virus synthesis**↵
[Codeforces GYM](https://codeforces.me/gym/100548/attachments)↵
↵
5. **The Problem to Slow Down You**↵
[Codeforces GYM](https://codeforces.me/gym/100548/attachments)↵
↵
**Advanced:**↵
↵
1. **100500 palidnromes**↵
[VJudge](https://acm.timus.ru/problem.aspx?space=1&num=2058)↵
↵
2. **Palindromadness**↵
[Codeforces GYM](https://codeforces.me/gym/102141/attachments)↵
↵
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.↵
↵
↵
↵
[cut]↵
↵
Comprehensive resource guide for Eertree (Palindromic Tree) data structure, inspired by Problem E from Codeforces Round 1059 (Div. 3). Includes tutorials, implementations, and practice problems.↵
