# Fibonacci words

I came across the following problem in my old Czech algorithm textbook, sadly came with no hints or solution.

"We define Fibonacci words as $F_{0}=a$, $F_{1}=b$, $F_{n+2}=F_{n}F_{n+1}$, where $a$ and $b$ are general letters. How in a given string (over a potentially large alphabet) can you find the longest Fibonacci's sub-word in linear time?"

I know a solution in quadratic time, but can't reduce it to linear. Can anyone point me to the right direction?

• What is the name of this old Czech algorithm textbook ;-) – Saeed Jan 29 '15 at 15:23
• Are sub-words required to be contiguous (i.e. factors) in this book? – Klaus Draeger Jan 30 '15 at 14:32

The obvious way to go is dynamic programming: let $F(i,j)$ store the two letters for which a Fibonacci word of order $i$ starts at position $j$, and calculate this by looking at $F(i-2,j)$ and $F(i-1,j+\operatorname{fib}(i))$. This takes $O(n \log n)$ time at most, because there are only logarithmically many possible values of $i$.
But I suspect that there can only be $O(n/\operatorname{fib}(i))$ positions for which $F(i-2,j)$ is nonempty (i.e. that when two Fibonacci words of the same length are present they can only overlap for up to a constant fraction of their length rather than most of their length). The nonempty positions of $F(i-2,j)$ are the only ones for which you need to do the (constant time) calculation for $F(i,j)$. So if my suspicion is true then you could speed it up to $O(n)$ by keeping track of a list of nonempty positions for each value of $i$ and using the list for $i-2$ to speed up the computation of the list for $i$.
If you store $F$ in an array the space would still be $O(n \log n)$ even after the speedup but this could be improved using a hashtable instead. Or alternatively you could store $F$ in a bit-packed array with $O(n)$ $\log n$-bit words (using the observation that you only need to know whether it's empty or not; you can find the two characters for each substring by looking at the first two of its positions in the input string).