The Number of Runs in a String: Improved Analysis of the Linear Upper Bound

DOI10.1007/11672142_14zbMATH Open1136.68621OpenAlexW1807114696MaRDI QIDQ5449797FDOQ5449797

Authors: Wojciech Rytter 

Publication date: 19 March 2008

Published in: STACS 2006 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11672142_14

Recommendations

• AN ASYMPTOTIC LOWER BOUND FOR THE MAXIMAL NUMBER OF RUNS IN A STRING
• On the Maximal Sum of Exponents of Runsin a String
• On the maximal sum of exponents of runs in a string
• A computational framework for determining run-maximal strings
• On the maximal number of cubic runs in a string
• On the structure of run-maximal strings
• Almost linear time computation of maximal repetitions in run length encoded strings
• Fast and Practical Algorithms for Computing All the Runs in a String
• A \(d\)-step approach to the maximum number of distinct squares and runs in strings

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorics on words (68R15)

Cited In (35)

• The total run length of a word
• Title not available (Why is that?)
• Optimal bounds for computing \({\alpha}\)-gapped repeats
• On the maximal sum of exponents of runs in a string
• The ``runs conjecture
• Upper bounds on distinct maximal (sub-)repetitions in compressed strings
• Tight Upper Bounds on Distinct Maximal (Sub-)Repetitions in Highly Compressible Strings
• Maximal repetitions in strings
• How many runs can a string contain?
• The maximal number of cubic runs in a word
• The structure of subword graphs and suffix trees of Fibonacci words
• Some results on the number of periodic factors in words
• Asymptotic behaviour of the maximal number of squares in standard Sturmian words
• Computing regularities in strings: a survey
• Bounds on Powers in Strings
• On the average number of regularities in a word
• A computational framework for determining run-maximal strings
• On the structure of run-maximal strings
• The three squares lemma revisited
• Repetitions in strings: algorithms and combinatorics
• A New Periodicity Lemma
• On primary and secondary repetitions in words
• Not So Many Runs in Strings
• On the maximal number of cubic runs in a string
• A Series of Run-Rich Strings
• The ``runs theorem
• Towards a Solution to the “Runs” Conjecture
• AN ASYMPTOTIC LOWER BOUND FOR THE MAXIMAL NUMBER OF RUNS IN A STRING
• The number of runs in a string
• On the density of Lyndon roots in factors
• Combinatorial Pattern Matching
• On the maximum number of cubic subwords in a word
• Three overlapping squares: the general case characterized \& applications
• Bannai et al. method proves the \(d\)-step conjecture for strings
• On the Maximal Sum of Exponents of Runsin a String

This page was built for publication: The Number of Runs in a String: Improved Analysis of the Linear Upper Bound

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