The "Runs" Theorem

Abstract

We give a new characterization of maximal repetitions (or runs) in strings based on Lyndon words. The characterization leads to a proof of what was known as the "runs" conjecture (Kolpakov \& Kucherov (FOCS '99)), which states that the maximum number of runs $\rho (n)$ in a string of length $n$ is less than $n$. The proof is remarkably simple, considering the numerous endeavors to tackle this problem in the last 15 years, and significantly improves our understanding of how runs can occur in strings. In addition, we obtain an upper bound of $3n$ for the maximum sum of exponents $\sigma (n)$ of runs in a string of length $n$, improving on the best known bound of $4.1n$ by Crochemore et al. (JDA 2012), as well as other improved bounds on related problems. The characterization also gives rise to a new, conceptually simple linear-time algorithm for computing all the runs in a string. A notable characteristic of our algorithm is that, unlike all existing linear-time algorithms, it does not utilize the Lempel-Ziv factorization of the string. We also establish a relationship between runs and nodes of the Lyndon tree, which gives a simple optimal solution to the 2-Period Query problem that was recently solved by Kociumaka et al. (SODA 2015).

simple proof with some more bounds

References in corpus (2)

• New Lower Bounds for the Maximum Number of Runs in a String
• On Bijective Variants of the Burrows-Wheeler Transform

Cited by in corpus (16)

• Algorithms to Compute the Lyndon Array
• Prefix frequency of lost positions
• Lyndon words versus inverse Lyndon words: queries on suffixes and bordered words
• Optimal searching of gapped repeats in a word
• Inducing the Lyndon Array
• Fewer runs than word length
• Faster Longest Common Extension Queries in Strings over General Alphabets
• Cartesian trees and Lyndon trees
• Computing Runs on a General Alphabet
• Fast Computation of Abelian Runs
• Counting Lyndon Subsequences
• Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries
• On the number of gapped repeats with arbitrary gap
• Grammar-compressed Self-index with Lyndon Words
• Detecting One-variable Patterns
• Efficiently computing runs on a trie