Shortest covers of all cyclic shifts of a string

DOI10.1016/j.tcs.2021.03.011zbMath1495.68252OpenAlexW4205167921MaRDI QIDQ5925516

Juliusz Straszyński, Wiktor Zuba, Maxime Crochemore, Tomasz Walen, Wojciech Rytter, Jakub Radoszewski, Costas S. Iliopoulos

Publication date: 14 April 2021

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

Full work available at URL: https://kclpure.kcl.ac.uk/portal/en/publications/shortest-covers-of-all-cyclic-shifts-of-a-string(17a7934e-9f89-46dc-849a-736c1e9b26c0).html

zbMATH Keywords

coverquasiperiodseedFibonacci string

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items

Finding the cyclic covers of a string, String Covering: A Survey, Abelian repetition threshold revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extracting powers and periods in a word from its runs structure
• Efficient seed computation revisited
• How many double squares can a string contain?
• Optimal superprimitivity testing for strings
• An on-line string superprimitivity test
• How many squares can a string contain?
• An optimal algorithm to compute all the covers of a string
• A characterization of the squares in a Fibonacci string
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Squares, cubes, and time-space efficient string searching
• Data structures and algorithms for the string statistics problem
• Covering a string
• On left and right seeds of a string
• A Linear-Time Algorithm for Seeds Computation
• The “Runs” Theorem
• Internal Pattern Matching Queries in a Text and Applications
• Shortest covers of all cyclic shifts of a string
• Computing the cover array in linear time