pith. sign in

arxiv: 0907.2157 · v1 · submitted 2009-07-13 · 💻 cs.DS · cs.DM

On the maximal number of highly periodic runs in a string

classification 💻 cs.DS cs.DM
keywords maximalrunsnumberstringboundhighlylengthperiod
0
0 comments X
read the original 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.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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.