Double-Ended Palindromic Trees in Linear Time
arXiv:2210.02292 · doi:10.1016/j.ic.2025.105379
Abstract
The palindromic tree (a.k.a. eertree) is a data structure that provides access to all palindromic substrings of a string. In this paper, we propose a dynamic version of eertree, called double-ended eertree, which supports online operations on the stored string, including double-ended queue operations, counting distinct palindromic substrings, and finding the longest palindromic prefix/suffix. At the heart of our construction, we identify a new class of substring occurrences, called surfaces, that are palindromic substring occurrences that are neither prefixes nor suffixes of any other palindromic substring occurrences, which is of independent interest. Surfaces characterize the link structure of all palindromic substrings in the eertree, thereby allowing a linear-time implementation of double-ended eertrees through a linear-time maintenance of surfaces.
Full version, 64 pages, 2 tables, 17 algorithms. Title changed, abstract improved, some proofs simplified, the persistent part removed for simplicity
References in corpus (14)
- Palindromic Richness
- A Subquadratic Algorithm for Minimum Palindromic Factorization
- A new characteristic property of rich words
- A note on palindromicity
- Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems
- Finding approximate palindromes in strings
- On the Combinatorics of Palindromes and Antipalindromes
- Extensions of rich words
- The Number of Distinct Subpalindromes in Random Words
- On Number of Rich Words
- Quantum Algorithm for Lexicographically Minimal String Rotation
- Equivalences between triangle and range query problems
- Quantum divide and conquer
- A Note on Quantum Divide and Conquer for Minimal String Rotation