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

(19)

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

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)