Logo image
Back
A new periodicity lemma
Journal article   Peer reviewed

A new periodicity lemma

K. Fan, W.F. Smyth and R.J. Simpson
Combinatorial Pattern Matching, Vol.3537, pp.257-265
2005
DOI: https://doi.org/10.1007/11496656_22
url
Link to Published Version *Subscription may be requiredView

Abstract

Given a string x = x[1..n], a repetition of period p in x is a substring u r  = x[i..i + rp − 1], p = |u|, r ≥ 2, where neither u = x[i..i + p − 1] nor x[i..i + (r + 1)p − 1] is a repetition. The maximum number of repetitions in any string x is well known to be Θ(nlog n). A run or maximal periodicity of period p in x is a substring u r t = x[i..i + rp + |t| − 1] of x, where u r is a repetition, t a proper prefix of x, and no repetition of period p begins at position i – 1 of x or ends at position i + rp + |t|. In 2000 Kolpakov and Kucherov showed that the maximum number ρ(n) of runs in any string x is O(n), but their proof was nonconstructive and provided no specific constant of proportionality. At the same time, they presented experimental data strongly suggesting that ρ(n) < n. In this paper, as a first step toward proving this conjecture, we present a periodicity lemma that establishes limitations on the number of squares, and their periods, that can occur over a specified range of positions in x. We then apply this result to specify corresponding limitations on the occurrence of runs.

Details

Metrics

64 Record Views
Logo image