A (finite) Fibonacci string F-n is defined as follows: F-0 = b, F-1 =
a; for every integer n greater than or equal to 2, F-n = Fn-1Fn-2. For
n greater than or equal to 1, the length of F-n is denoted by f(n) =
/F-n/. The infinite Fibonacci string F is the string which contains ev
ery F-n, n greater than or equal to 1, as a prefix. Apart from their g
eneral theoretical importance, Fibonacci strings are often cited as wo
rst-case examples for algorithms which compute all the repetitions or
all the ''Abelian squares'' in a given string. In this paper we provid
e a characterization of all the squares in F, hence in every prefix F-
n; this characterization naturally gives rise to a Theta(f(n)) algorit
hm 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 occ
ur consecutively, in ''runs'', the number of which is Theta(f(n)). By
contrast, the known general algorithms for the computation of the repe
titions 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 stri
ng F-n.