Counting Palindromes in Substrings

DOI10.1007/978-3-319-67428-5_25zbMath1454.68209OpenAlexW2751037589MaRDI QIDQ5150941

Mikhail Rubinchik, Arseny M. Shur

Publication date: 16 February 2021

Published in: String Processing and Information Retrieval (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-67428-5_25

zbMATH Keywords

online algorithmpalindromestring algorithmcounting palindromeseertree

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics on words (68R15) Data structures (68P05) Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Related Items

Internal shortest absent word queries in constant time and linear space, Finding top-\(k\) longest palindromes in substrings, Algorithms and combinatorial properties on shortest unique palindromic substrings, Experimental evaluation of algorithms for computing quasiperiods, Internal dictionary matching, Efficient representation and counting of antipower factors in words

Uses Software

• EERTREE

Cites Work

• Unnamed Item
• Unnamed Item
• A subquadratic algorithm for minimum palindromic factorization
• Counting distinct palindromes in a word in linear time
• Palindromic rich words and run-length encodings
• Palindromic richness
• Making data structures persistent
• EERTREE: an efficient data structure for processing palindromes in strings
• ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
• Diverse Palindromic Factorization Is NP-complete
• 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
• Computing Palindromic Factorizations and Palindromic Covers On-line
• Pal k is Linear Recognizable Online
• Uniqueness Theorems for Periodic Functions
• Episturmian words and some constructions of de Luca and Rauzy