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 RM …

Squares (fragments of the form xx, for some string x) are arguably the most natural type of
repetition in strings. The basic algorithmic question concerning squares is to check if a given …

The cornerstone of any algorithm computing all repetitions in strings of length n in O (n) time
is the fact that the number of maximal repetitions (runs) is linear. Therefore, the most …

The article is an overview of basic issues related to repetitions in strings, concentrating on
algorithmic and combinatorial aspects. This area is important both from theoretical and …

String matching is one of the oldest algorithmic techniques, yet still one of the most
pervasive in computer science. The past 20 years have seen technological leaps in …

A run in a string is a maximal periodic substring. For example, the string $\texttt {bananatree}
$ contains the runs $\texttt {anana}=(\texttt {an})^{3/2} $ and $\texttt {ee}=\texttt {e}^ 2$. There …

The “runs” conjecture, proposed by Kolpakov and Kucherov (1999)[7], states that the
number of occurrences of maximal repetitions (runs) in a string of length n, runs (n), is at …

We give a new characterization of maximal repetitions (or runs) in strings, using a tree
defined on recursive standard factorizations of Lyndon words, called the Lyndon tree. The …

Internationally recognised researchers look at developing trends in combinatorics with
applications in the study of words and in symbolic dynamics. They explain the important …

Since the work of Kolpakov and Kucherov in 5, 6, it is known that ρ (n), the maximal number
of runs in a string, is linear in the length n of the string. A lower bound of 3/(1+5)n∼0.927n …