CLR cover
Previous problem

Problem 56: Comparing Suffixes of a Fibonacci Word

Next problem

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 .

  1. Show how to compare any two suffixes of in time .
  2. Improve the running time to .
For (A) use the algorithm of Problem 6.

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.