Palavras de Fibonacci

Me deparei com o seguinte problema no meu antigo livro didático de algoritmo tcheco, que infelizmente não apresentava dicas ou soluções.

"Definimos palavras de Fibonacci como , F 1 = b , F n + 2 = F n F n + 1 , onde a e b são letras gerais. Como em uma determinada string (sobre um alfabeto potencialmente grande) você pode encontrar a sub-palavra mais longa de Fibonacci no tempo linear? "$F_{0}=a$$F_{1}=b$$F_{n+2}=F_{n}F_{n+1}$$a$$b$

Conheço uma solução em tempo quadrático, mas não posso reduzi-la a linear. Alguém pode me indicar a direção certa?

$F(i,j)$$i$$j$$F(i-2,j)$$F(i-1,j+\operatorname{fib}(i))$$O(n \log n)$$i$.

$O(n/\operatorname{fib}(i))$$F(i-2,j)$$F(i-2,j)$$F(i,j)$$O(n)$$i$$i-2$$i$

$F$$O(n \log n)$$F$$O(n)$ $\log n$