Journal article
The covers of a circular Fibonacci string
Journal of Combinatorial Mathematics and Combinatorial Computing, Vol.26, pp.227-236
1998
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).
Details
- Title
- The covers of a circular Fibonacci string
- Authors/Creators
- C.S. Iliopoulos (Author/Creator)D. Moore (Author/Creator)W.F. Smyth (Author/Creator)
- Publication Details
- Journal of Combinatorial Mathematics and Combinatorial Computing, Vol.26, pp.227-236
- Publisher
- Charles Babbage Research Centre
- Identifiers
- 991005541126307891
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
- Publisher URL
- http://www.combinatorialmath.ca/jcmcc/
Metrics
88 File views/ downloads
79 Record Views