A NEW PERIODICITY LEMMA

摘要

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 Θ(n log n). A run or maximal periodicity of period p in x is a substring u~rt = x[i..i + rp+|t| — 1] of x, where u~r is a repetition, t is 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 and Kucherov [J. Discrete Algorithms, 1 (2000), pp. 159—186] 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. Related work by Fraenkel and Simpson [J. Combin. Theory Ser. A., 82 (1998), pp. 112-120] showed that the maximum number σ(n) of distinct squares in any string x satisfies σ(n) < 2n, while experiment again encourages the belief that in fact σ(n) < n. In this paper, as a first step toward proving these conjectures, we present a periodicity lemma that establishes limitations on the number and range of periodicities 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.