Fibonacci Wörter

11

Ich bin in meinem alten tschechischen Algorithmus-Lehrbuch auf folgendes Problem gestoßen, leider ohne Hinweise oder Lösung.

"Wir definieren Fibonacci-Wörter als , F 1 = b , F n + 2 = F n F n + 1 , wobei a und b allgemeine Buchstaben sind. Wie können Sie in einer bestimmten Zeichenfolge (über einem potenziell großen Alphabet) das längste Fibonacci-Unterwort in linearer Zeit finden? "F0=aF1=bFn+2=FnFn+1ab

Ich kenne eine Lösung in quadratischer Zeit, kann sie aber nicht auf linear reduzieren. Kann mich jemand in die richtige Richtung weisen?

Fanda
quelle
3
Wie heißt dieses alte tschechische Algorithmus-Lehrbuch?
Saeed
Müssen Unterwörter in diesem Buch zusammenhängend sein (dh Faktoren)?
Klaus Draeger

Antworten:

12

F(i,j)ijF(i2,j)F(i1,j+fib(i))O(nlogn)i.

O(n/fib(i))F(i2,j)F(i2,j)F(i,j)O(n)ii2i

FO(nlogn)FO(n) logn

David Eppstein
quelle
Können Sie mir sagen, warum Sie dachten, dass dynamische Programmierung die beste Wahl für dieses Problem ist? Wo werden wir Probleme haben, wenn wir eine statische Programmierung wie C verwenden ?
Tarit Goswami
1
Dynamische Programmierung ist eine Algorithmus-Entwurfstechnik, keine Klasse von Programmiersprachen.
David Eppstein