Catalog Home Page

A new periodicity lemma

Fan, K., Smyth, W.F. and Simpson, R.J. (2005) A new periodicity lemma. Lecture Notes in Computer Science, 3537 . pp. 257-265.

Link to Published Version:
*Subscription may be required


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.

Publication Type: Journal Article
Publisher: Springer Verlag
Copyright: 2005 Springer-Verlag Berlin Heidelberg
Item Control Page Item Control Page