On the maximal number of highly periodic runs in a string

Details On the maximal number of highly periodic runs in a string On the maximal number of highly periodic runs in a string

2009-07-13

arxiv.org/abs/0907.2157v1

Computer Science

Data Structures and Algorithms

8 pages, 2 figures

Scientific paper

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$.

Affiliated with

Also associated with

No associations

Rating

On the maximal number of highly periodic runs in a string does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the maximal number of highly periodic runs in a string, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the maximal number of highly periodic runs in a string will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-100846