Counting distinct palindromes in a word in linear time

DOI10.1016/j.ipl.2010.07.018zbMath1234.68329DBLPjournals/ipl/GroultPR10OpenAlexW1972084722WikidataQ96738845 ScholiaQ96738845MaRDI QIDQ407601

Richard Groult, Élise Prieur, Gwenaël Richomme

Publication date: 27 March 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.07.018

zbMATH Keywords

palindromepalindromic richnesspalindromic fullness

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (16)

Improved upper bounds on all maximal \(\alpha\)-gapped repeats and palindromes ⋮ EERTREE: an efficient data structure for processing palindromes in strings ⋮ Palindrome pattern matching ⋮ An efficient algorithm for the longest common palindromic subsequence problem ⋮ Enumeration of two dimensional palindromes ⋮ Tight bound for the number of distinct palindromes in a tree ⋮ Finding top-\(k\) longest palindromes in substrings ⋮ Algorithms and combinatorial properties on shortest unique palindromic substrings ⋮ Computing longest palindromic substring after single-character or block-wise edits ⋮ Palindromic trees for a sliding window and its applications ⋮ Counting Palindromes in Substrings ⋮ Greedy Palindromic Lengths ⋮ Palindrome Pattern Matching ⋮ Internal dictionary matching ⋮ Faster queries for longest substring palindrome after block edit ⋮ Longest substring palindrome after edit

Cites Work

• Unnamed Item
• Parallel detection of all palindromes in a string
• Computing longest previous factor in linear time and applications
• Palindromic richness
• Palindrome recognition in real time by a multitape Turing machine
• Sturmian words: structure, combinatorics, and their arithmetics
• Palindrome complexity.
• Finding all periods and initial palindromes of a string in parallel
• Burrows-Wheeler transform and palindromic richness
• ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Algorithms on Strings, Trees and Sequences
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• Episturmian words: a survey
• Episturmian words and some constructions of de Luca and Rauzy

This page was built for publication: Counting distinct palindromes in a word in linear time