×

zbMATH — the first resource for mathematics

EERTREE: an efficient data structure for processing palindromes in strings. (English) Zbl 06562495
Lipták, Zsuzsanna (ed.) et al., Combinatorial algorithms. 26th international workshop, IWOCA 2015, Verona, Italy, October 5–7, 2015. Revised selected papers. Cham: Springer (ISBN 978-3-319-29515-2/pbk; 978-3-319-29516-9/ebook). Lecture Notes in Computer Science 9538, 321-333 (2016).
Summary: 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.
For the entire collection see [Zbl 1331.68018].

MSC:
68Rxx Discrete mathematics in relation to computer science
68Wxx Algorithms in computer science
Software:
EERTREE; OEIS
PDF BibTeX XML Cite
Full Text: DOI