|
Problem 56: Comparing Suffixes of a Fibonacci Word
|
|
The structure of Fibonacci words, like that of Thue-Morse words, is an
example of a situation in which some algorithms can be optimised to run in
logarithmic time with respect to the length of words.
The problem is concerned with a fast lexicographic comparison between
two suffixes of a finite Fibonacci word, which shows such a phenomenon.
We deal with a slightly shortened version of Fibonacci words to simplify
arguments.
Let be the th Fibonacci word with the last
two letters deleted, that is, ,
for .
Let also be the th suffix
of .
The comparison between suffixes of is efficiently reduced to the
comparison of their compact representation of logarithmic length implied by
their logarithmic-size decomposition (property below).
Factors of the decomposition are the reverse of
Fibonacci words.
The first factors are , , and
.
Observe that and starts with the
letter if and only if is even.
Property
For , uniquely factorises as ,
where and for
.
Related to the factorisation let .
-
Show how to compare any two suffixes of
in time .
-
Improve the running time to .
References
W. Rytter. The structure of subword graphs and suffix trees of Fibonacci
words. Theor. Comput. Sci., 363(2):211-223, 2006.
B. Walczak. A simple representation of subwords of the Fibonacci word.
Inf. Process. Lett., 110(21):956-960, 2010.