On the maximal number of highly periodic runs in a string

Abstract

A run is a maximal occurrence of a repetition $v$ with a period $p$ such that $2p\le |v|$. The maximal number of runs in a string of length $n$ was studied by several authors and it is known to be between $0.944n$ and $1.029n$. We investigate highly periodic runs, in which the shortest period $p$ satisfies $3p\le |v|$. We show the upper bound $0.5n$ on the maximal number of such runs in a string of length $n$ and construct a sequence of words for which we obtain the lower bound $0.406n$.

8 pages, 2 figures