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

DOI10.1007/11672142_14MaRDI QIDQ5449797zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(35)

• On the Maximal Sum of Exponents of Runsin a String
• The total run length of a word
• On the maximal sum of exponents of runs in a string
• Optimal bounds for computing \({\alpha}\)-gapped repeats
• The ``runs conjecture
• scientific article; zbMATH DE number 7651171 (Why is no real title available?)
• Upper bounds on distinct maximal (sub-)repetitions in compressed strings
• Maximal repetitions in strings
• How many runs can a string contain?
• The maximal number of cubic runs in a word
• Tight Upper Bounds on Distinct Maximal (Sub-)Repetitions in Highly Compressible Strings
• The structure of subword graphs and suffix trees of Fibonacci words
• Some results on the number of periodic factors in words
• Computing regularities in strings: a survey
• Asymptotic behaviour of the maximal number of squares in standard Sturmian words
• 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
• On the density of Lyndon roots in factors
• The number of runs in a string
• On the maximum number of cubic subwords in a word
• Combinatorial Pattern Matching
• Three overlapping squares: the general case characterized \& applications
• Bannai et al. method proves the \(d\)-step conjecture for strings

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)