# Longest Fibonacci word

We define Fibonacci words as: $$F_0 = a, F_1 = b, F_{n+2} = F_n F_{n+1}$$, $$a, b$$ can be any symbols.

How can we find the longest Fibonacci sub-word in a given string in linear time?

This question is similar to: Complexity of a naive algorithm for finding the longest Fibonacci substring But I'm in particular interested if there is an $$O(n)$$ solution.

First let me consider the Fibonacci strings I am used to: $$f_{n+2} = f_{n+1} f_n$$. Observe that each $$f_{n+2}$$ is a prefix of the previous $$f_{n+1}$$. This makes it simple to construct the next Fibonacci string from the previous one. For instance keep a reference to the last prefix and copy that prefix after the current Fibonacci string.
Representing all substrings of a string can be done by constructing the suffix-tree or suffix-array of that string. Magically this suffix-tree $$T$$ can be constructed in linear time. Start reading Fibonacci string $$f_k$$ in $$T$$, and once we have found this string extend the search into $$f_{k+1}$$, etcetera. This is possible because of the prefix property of Fibonacci strings.