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

A New Periodicity Lemma

Fan, K., Puglisi, S.J., Smyth, W.F. and Turpin, A. (2006) A New Periodicity Lemma. SIAM Journal on Discrete Mathematics, 20 (3). pp. 656-668.

Link to Published Version:
*Subscription may be required


Given a string $\s{x}=\s{x}[1..n]$, a repetition of period p in {\mbox{\boldmath x}} is a substring ${\mbox{\boldmath u}}^r = \break {\mbox{\boldmath x}}[i..i\+ rp\- 1]$, $p = |{\mbox{\boldmath u}}|$, $r \ge 2$, where neither ${\mbox{\boldmath u}} = {\mbox{\boldmath x}}[i..i\+ p\- 1]$ nor ${\mbox{\boldmath x}}[i..i\+ (r\+ 1)p\- 1]$ is a repetition. The maximum number of repetitions in any string {\mbox{\boldmath x}} is well known to be $\Theta(n\log n)$. A run or maximal periodicity of period p in {\mbox{\boldmath x}} is a substring ${\mbox{\boldmath u}}^r{\mbox{\boldmath t}} = {\mbox{\boldmath x}}[i..i\+ rp\+ |{\mbox{\boldmath t}}|\- 1]$ of {\mbox{\boldmath x}}, where ${\mbox{\boldmath u}}^r$ is a repetition, {\mbox{\boldmath t}} is a proper prefix of {\mbox{\boldmath u}}, and no repetition of period p begins at position $i\- 1$ of {\mbox{\boldmath x}} or ends at position $i\+ rp\+ |{\mbox{\boldmath t}}|$. In 2000 Kolpakov and Kucherov [J. Discrete Algorithms, 1 (2000), pp. 159–186] showed that the maximum number $\rho(n)$ of runs in any string {\mbox{\boldmath 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 $\rho(n) < n$. Related work by Fraenkel and Simpson [J. Combin. Theory Ser. A., 82 (1998), pp. 112–120] showed that the maximum number $\sigma(n)$ of distinct squares in any string {\mbox{\boldmath x}} satisfies $\sigma(n) < 2n$, while experiment again encourages the belief that in fact $\sigma(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 {\mbox{\boldmath x}}. We then apply this result to specify corresponding limitations on the occurrence of runs.

Item Type: Journal Article
Publisher: Society for Industrial and Applied Mathematics
Copyright: © 2006 Society for Industrial and Applied Mathematics Read More:
Item Control Page Item Control Page