Fibonacci Wörter

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 , , , wobei und 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? " $F_{0}=a$ $F_{1}=b$ $F_{n+2}=F_{n}F_{n+1}$ $a$ $b$

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

string-matching string-search Fanda
quelle

Wie heißt dieses alte tschechische Algorithmus-Lehrbuch?

Saeed

Müssen Unterwörter in diesem Buch zusammenhängend sein (dh Faktoren)?

Klaus Draeger

Antworten:

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

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

Dynamische Programmierung ist eine Algorithmus-Entwurfstechnik, keine Klasse von Programmiersprachen.

David Eppstein