The covers of a circular Fibonacci string
Costas S. Iliopoulos, Dennis Moore, W.F. Smyth · 1998
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 C(F k ) and show that they are \\Theta(jF k j 2 ) in number. We show also that, by making use of an appropriate encoding, these covers can be reported in \\Theta(jF k j) 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). 1. Introduction For any nonnegative integer k, a Fibonacci string F k is defined as follows: F 0 = b, F 1 = a, while for k 2, F k = F k\\Gamma1 F k\\Gamma2 . The number of elements in F k is called its length, denoted by f k = jF k j, where of course f k is a Fibonacci number. For every pair of integers i and j satisfying 1 i j f k , F k [i::j] denotes a substring of F k ; when i = j, we w...