Catalog Home Page

The covers of a circular Fibonacci string

Iliopoulos, C.S., Moore, D. and Smyth, W.F. (1998) The covers of a circular Fibonacci string. Journal of Combinatorial Mathematics and Combinatorial Computing, 26 . pp. 227-236.

[img]
Preview
PDF - Authors' Version
Download (168kB)

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

Publication Type: Journal Article
Publisher: Charles Babbage Research Centre
Publishers Website: http://www.combinatorialmath.ca/jcmcc/
URI: http://researchrepository.murdoch.edu.au/id/eprint/27561
Item Control Page Item Control Page

Downloads

Downloads per month over past year