The Covers Of A Circular Fibonacci String

Abstract

Fibonacci strings turn out to constitute worst cases for a number of computer algorithms which find generic patterns in strings. Examples of such patterns are repetitions, Abelian squares, and “covers”. In particular, we characterize in this paper the covers of a circular Fibonacci string $\mathcal{C}(F_k)$ and show that they are $\mathrm{\Theta }(|F_k{|}^2)$ in number. We show also that, by making use of an appropriate encoding, these covers can be reported in $\mathrm{\Theta }(|F_k|)$ time. By contrast, the fastest known algorithm for computing the covers of an arbitrary circular string of length $n$ requires time $O(n\log n)$.