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

Iliopoulos, C.S., Moore, D. and Smyth, W.F. (1996) A linear algorithm for computing all the squares of a Fibonacci string. In: Computing: The Australasian Theory Symposium (CATS '96), 29 - 30 January 1996, Melbourne, Australia

 Preview

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

Publication Type: Conference Paper http://researchrepository.murdoch.edu.au/id/eprint/27530
 Item Control Page