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

*Subscription may be required

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

Publication Type: | Journal Article |
---|---|

Publisher: | Springer Verlag |

Copyright: | 2005 Springer-Verlag Berlin Heidelberg |

URI: | http://researchrepository.murdoch.edu.au/id/eprint/27891 |

Item Control Page |