###
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