A fast algorithm for finding the positions of all squares in a run-length encoded string

DOI10.1016/j.tcs.2009.05.032zbMath1175.68572OpenAlexW2000332055MaRDI QIDQ837185

N. E. Zubov

Publication date: 10 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.05.032

zbMATH Keywords

squaresrun-length encodingrepetitiondivide-and-conquer

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Related Items

Distinct squares in run-length encoded strings, Efficient retrieval of approximate palindromes in a run-length encoded string, Double string tandem repeats

Cites Work

• Unnamed Item
• Unnamed Item
• A coarse-grained multicomputer algorithm for the detection of repetitions
• An efficient algorithm for online square detection
• An optimal algorithm for computing the repetitions in a word
• Optimal off-line detection of repetitions in a string
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Transducers and repetitions
• Detecting leftmost maximal periodicities
• Detection of periodicities and string-matching in real time
• An O(n log n) algorithm for finding all repetitions in a string
• Fast Pattern Matching in Strings
• Algorithms on Strings, Trees and Sequences
• Jewels of Stringology
• Simple and flexible detection of contiguous repeats using a suffix tree