EERTREE: an efficient data structure for processing palindromes in strings

DOI10.1016/j.ejc.2017.07.021zbMath1374.68131DBLPjournals/ejc/RubinchikS18arXiv1506.04862OpenAlexW2964071288WikidataQ90726647 ScholiaQ90726647MaRDI QIDQ1678105

Arseny M. Shur, Mikhail Rubinchik

Publication date: 14 November 2017

Published in: Lecture Notes in Computer Science, European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.04862

zbMATH Keywords

linear-size data structurepalindromic substrings

Mathematics Subject Classification ID

Combinatorics on words (68R15) Data structures (68P05)

Related Items (25)

Prefix palindromic length of the Thue-Morse word ⋮ Minimal unique palindromic substrings after single-character substitution ⋮ On Morphisms Preserving Palindromic Richness ⋮ Palindromic decompositions with gaps and errors ⋮ Palindromic length and reduction of powers ⋮ EERTREE: an efficient data structure for processing palindromes in strings ⋮ The palindromization map ⋮ Finding top-\(k\) longest palindromes in substrings ⋮ Palindromic length of words and morphisms in class \(\mathcal{P}\) ⋮ Maximal degenerate palindromes with gaps and mismatches ⋮ Algorithms and combinatorial properties on shortest unique palindromic substrings ⋮ Palindromic Decompositions with Gaps and Errors ⋮ Ostrowski-automatic sequences: theory and applications ⋮ Computing longest palindromic substring after single-character or block-wise edits ⋮ Palindromic trees for a sliding window and its applications ⋮ On prefix palindromic length of automatic words ⋮ Detecting One-Variable Patterns ⋮ Counting Palindromes in Substrings ⋮ Diverse Palindromic Factorization is NP-Complete ⋮ Greedy Palindromic Lengths ⋮ Unnamed Item ⋮ Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings ⋮ Palindromic rich words and run-length encodings ⋮ EERTREE ⋮ Comparing Degenerate Strings

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On palindromic factorization of words
• A subquadratic algorithm for minimum palindromic factorization
• Counting distinct palindromes in a word in linear time
• Palindromic richness
• Making data structures persistent
• EERTREE: an efficient data structure for processing palindromes in strings
• Algorithms for pattern matching and discovery in RNA secondary structure
• On-line construction of suffix trees
• The affix array data structure and its applications to RNA secondary structure analysis
• Space Efficient Linear Time Construction of Suffix Arrays
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• A Linear-Time On-Line Recognition Algorithm for ``Palstar
• Fast Pattern Matching in Strings
• Algorithms on Strings, Trees and Sequences
• On the palindromic decomposition of binary words
• The Number of Distinct Subpalindromes in Random Words
• Palindromic length in linear time
• Computing Palindromic Factorizations and Palindromic Covers On-line
• Pal k is Linear Recognizable Online
• Episturmian words and some constructions of de Luca and Rauzy
• Watson-Crick palindromes in DNA computing

This page was built for publication: EERTREE: an efficient data structure for processing palindromes in strings