A linear algorithm for computing all the squares of a Fibonacci string


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


Abstract

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


Conference Home Page