On the maximal sum of exponents of runs in a string

DOI10.1016/j.jda.2011.12.016zbMath1247.68335OpenAlexW2095479759MaRDI QIDQ450542

Marcin Kubica, Maxime Crochemore, Wojciech Rytter, Jakub Radoszewski, Tomasz Walen

Publication date: 13 September 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.12.016

zbMATH Keywords

lower boundrunsexponents of repetitionsrepetitions in strings

Mathematics Subject Classification ID

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

Related Items

Two strings at Hamming distance 1 cannot be both quasiperiodic, Searching of gapped repeats and subrepetitions in a word, The total run length of a word, On palindromic factorization of words, The “Runs” Theorem, On the number of gapped repeats with arbitrary gap, Average number of occurrences of repetitions in a necklace, Optimal bounds for computing \({\alpha}\)-gapped repeats, Some results on the number of periodic factors in words

Cites Work

• Maximal repetitions in strings
• How many runs can a string contain?
• Repetitions in strings: algorithms and combinatorics
• The number of runs in a string
• Towards a Solution to the “Runs” Conjecture
• Analysis of Maximal Repetitions in Strings
• AN ASYMPTOTIC LOWER BOUND FOR THE MAXIMAL NUMBER OF RUNS IN A STRING
• Not So Many Runs in Strings
• On the Maximal Number of Cubic Runs in a String
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item