Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Some restrictions on periodicity in strings

Puglisi, S.J., Smyth, W.F. and Turpin, A. (2005) Some restrictions on periodicity in strings. In: 16th Australasian Workshop on Combinatorial Algorithms (AWOCA) 2005, 18 - 21 September 2005, Ballarat, VIC



Given a string x = x[1..n], a repetition of period p in x is a substring ur = 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 Θ(n log n). A run or maximal periodicity of period p in x is a substring urt = x[i..i+rp+|t|−1] of x, where ur is a repetition, t a proper prefix of u, and no repetition of period p begins at position i−1 of x or ends at position i+rp+|t|. In 2000 Kolpakov & 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. that the maximum any string x again encourages the belief that in fact σ(n) < n. Recently, Fan et al.(“A new periodicity lemma”, Sixteenth Annual Symp. Combin. Pattern Matching, 2005) took a first step toward proving these conjectures, by presenting results that establish limitations on the number of squares of a specified range of periods that can occur over a specified range of positions in x. In this paper, we further tighten these restrictions by showing how the existence of two squares u and v (v longer than u) at the same position i in x limits the occurrence of smaller squares with period w ∈ (|v| − |u|, |u|) in the neighborhood around i.

Item Type: Conference Paper
Item Control Page Item Control Page


Downloads per month over past year