%0 Journal Article
%T On the maximal number of highly periodic runs in a string
%A Maxime Crochemore
%A Costas Iliopoulos
%A Marcin Kubica
%A Jakub Radoszewski
%A Wojciech Rytter
%A Tomasz Walen
%J Computer Science
%D 2009
%I arXiv
%X 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.944 n$ and $1.029 n$. 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.406 n$.
%U http://arxiv.org/abs/0907.2157v1