Advertisement
Published in:
2006 | OriginalPaper | Chapter
The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A
run
(or a
maximal repetition
) in a string is an inclusion-maximal periodic segment in a string. Let
ρ
(
n
) be the maximal number of runs in a string of length
n
. It has been shown in [8] that
ρ
(
n
)=
O
(
n
), the proof was very complicated and the constant coefficient in
O
(
n
) has not been given explicitly. We propose a new approach to the analysis of runs based on the properties of subperiods: the periods of periodic parts of the runs. We show that
ρ
(
n
) ≤ 5
n
. Our proof is inspired by the results of [4], where the role of new periodicity lemmas has been emphasized.