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

DOI10.1016/J.TCS.2009.05.032MaRDI QIDQ837185zbMATH OpenOpenAlexFDO

Authors 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

divide-and-conquerrepetitionrun-length encodingsquares

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3913712
• Factorizing a String into Squares in Linear Time
• Computing and Combinatorics
• An Optimal O(\log \log N)-Time Parallel Algorithm for Detecting all Squares in a String
• Fast and Practical Algorithms for Computing All the Runs in a String

Cites work

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

Cited in

(5)

• Squares, cubes, and time-space efficient string searching
• Double string tandem repeats
• Efficient retrieval of approximate palindromes in a run-length encoded string
• Computing all distinct squares in linear time for integer alphabets
• Distinct squares in run-length encoded strings

This page was built for publication: A fast algorithm for finding the positions of all squares in a run-length encoded string

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