Counting distinct palindromes in a word in linear time

DOI10.1016/J.IPL.2010.07.018MaRDI QIDQ407601zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Richard Groult, Élise Prieur, Gwénaë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)

Recommendations

• Counting palindromes in substrings
• Palindromic length in linear time
• Tight bound for the number of distinct palindromes in a tree
• On the number of rich words
• Properties of palindromes in finite words

Cites work

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

Cited in

(17)

• Enumeration of two dimensional palindromes
• An efficient algorithm for the longest common palindromic subsequence problem
• Palindrome pattern matching
• Palindrome pattern matching
• Palindromic trees for a sliding window and its applications
• Improved upper bounds on all maximal \(\alpha\)-gapped repeats and palindromes
• Internal dictionary matching
• scientific article; zbMATH DE number 7696009 (Why is no real title available?)
• Faster queries for longest substring palindrome after block edit
• Longest substring palindrome after edit
• Counting palindromes in substrings
• Tight bound for the number of distinct palindromes in a tree
• Greedy palindromic lengths
• On longest common property preserved substring queries
• Computing longest palindromic substring after single-character or block-wise edits
• Algorithms and combinatorial properties on shortest unique palindromic substrings
• Improved estimates for the number of privileged words

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q407601)