Costas S.
Iliopoulos
Department of Computer Science,
King's College London
London WC2R 2LS, England.
csi@dcs.kcl.ac.uk
Dennis Moore
School of Computing
Curtin University of Technology,
GPO U 1987, Perth 6001, Australia.
moore@cs.curtin.edu.au
W.F. Smyth
Department of Computer Science & Systems
McMaster University
Hamilton, Ontario
Canada L8S 4K1
smyth@mcmaster.ca
A (finite) Fibonacci string $F_n$ is defined as follows: $F_0 = b$, $F_1 = a$; for every integer $n \ge 2$, $F_n = F_{n-1}F_{n- 2}$. For $n \ge 1$, the length of $F_n$ is denoted by $f_n = |F_n|$, while it is convenient to define $f_0 \equiv 0$. The infinite Fibonacci string $F$ is the string which contains every $F_n$, $n \ge 1$, as a prefix. Apart from their general theoretical importance, Fibonacci strings are often cited as worst case examples for algorithms which compute all the repetitions or all the ``Abelian squares'' in a given string. In this paper we provide a characterization of all the squares in $F$, hence in every prefix $F_n$; this characterization naturally gives rise to a $\Theta(f_n)$ algorithm which specifies all the squares of $F_n$ in an appropriate encoding. This encoding is made possible by the fact that the squares of $F_n$ occur consecutively, in ``runs'', the number of which is $\Theta(f_n)$. By contrast, the known general algorithms for the computation of the repetitions in an arbitrary string require $\Theta(f_n\log f_n)$ time (and produce $\Theta(f_n\log f_n)$ outputs) when applied to a Fibonacci string $F_n$.