Palabras de Fibonacci

Me encontré con el siguiente problema en mi antiguo libro de texto de algoritmo checo, lamentablemente no tuve pistas ni solución.

"Definimos las palabras de Fibonacci como , F 1 = b , F n + 2 = F n F n + 1 , donde a y b son letras generales. Cómo en una cadena dada (sobre un alfabeto potencialmente grande) puede encuentra la sub-palabra de Fibonacci más larga en tiempo lineal? "$F_{0}=a$$F_{1}=b$$F_{n+2}=F_{n}F_{n+1}$$a$$b$

Conozco una solución en tiempo cuadrático, pero no puedo reducirla a lineal. ¿Alguien puede señalarme en la dirección correcta?

$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$