Distinct squares in run-length encoded strings

DOI10.1016/J.TCS.2010.08.031zbMath1208.68166OpenAlexW2066290715MaRDI QIDQ606988

Sumit K. Garg

Publication date: 19 November 2010

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

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

zbMATH Keywords

squaresrun-length encodingrepetition\(rc\)-occurrence

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• A fast algorithm for finding the positions of all squares in a run-length encoded string
• Maximal repetitions in strings
• How many squares can a string contain?
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Detecting leftmost maximal periodicities
• Squares, cubes, and time-space efficient string searching
• A note on the number of squares in a word
• A simple proof that a word of length \(n\) has at most \(2n\) distinct squares
• An O(n log n) algorithm for finding all repetitions in a string
• Fast Pattern Matching in Strings
• Jewels of Stringology

This page was built for publication: Distinct squares in run-length encoded strings