EERTREE: An Efficient Data Structure for Processing Palindromes in Strings

2015/06/16 by Rubinchik, Mikhail, Shur, Arseny M. · 3 citations
#68P05 #68W32 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.1506.04862

Abstract

We propose a new linear-size data structure which provides a fast access to all palindromic substrings of a string or a set of strings. This structure inherits some ideas from the construction of both the suffix trie and suffix tree. Using this structure, we present simple and efficient solutions for a number of problems involving palindromes.

Cited by

• Small palindromic lengths in free groups and word equations with antimorphisms
• Compact representation of maximal palindromes
• Combinatorics of Palindromes

Related

• Double-Ended Palindromic Trees in Linear Time
• Finding Top-k Longest Palindromes in Substrings
• Compact representation of maximal palindromes
• Palindrome Recognition In The Streaming Model
• Finding Approximate Palindromes in Strings Quickly and Simply