Słowa Fibonacciego

11

W moim starym czeskim podręczniku algorytmów natknąłem się na następujący problem, niestety przyszedł bez wskazówek i rozwiązania.

„Określamy Fibonacciego słów , , , gdzie i są ogólnie literami. Jak w danej ciąg (ponad potencjalnie dużym alfabetem) czy możesz znaleźć najdłuższe pod-słowo Fibonacciego w czasie liniowym? ”F 1 = b F n + 2 = F n F n + 1 a bF0=aF1=bFn+2=FnFn+1ab

Znam rozwiązanie w czasie kwadratowym, ale nie mogę zredukować go do liniowego. Czy ktoś może wskazać mi właściwy kierunek?

Fanda
źródło
3
Jak nazywa się ten stary czeski podręcznik algorytmu ;-)
Saeed
Czy podteksty muszą być ciągłe (tj. Czynniki) w tej książce?
Klaus Draeger,

Odpowiedzi:

12

Oczywistym sposobem jest programowanie dynamiczne: pozwól zapisać dwie litery, dla których słowo porządku Fibonacciego zaczyna się w pozycji , i oblicz to, patrząc na i . Zajmuje to najwyżej , ponieważ istnieje tylko logarytmicznie wiele możliwych wartości .i j F ( i - 2 , j ) F ( i - 1 , j + fib ( i ) ) O ( n log n ) iF(i,j)ijF(i2,j)F(i1,j+fib(i))O(nlogn)i

Podejrzewam jednak, że mogą istnieć tylko pozycje dla których jest niepuste (tzn. Gdy obecne są dwa słowa Fibonacciego o tej samej długości, mogą one tylko nakładają się na siebie do stałej części ich długości, a nie przez większość ich długości). Niepuste pozycje są jedynymi, dla których należy wykonać obliczenia (stały czas) dla . Więc jeśli moje podejrzenie jest prawdziwe, możesz to przyspieszyć do , śledząc listę niepustych pozycji dla każdej wartości i używając listy dla aby przyspieszyć obliczanie listy dla .F ( i - 2 , j ) F ( i - 2 , j ) F ( i , j ) O ( n ) i i - 2 iO(n/fib(i))F(i2,j)F(i2,j)F(i,j)O(n)ii2i

Jeśli przechowujesz w tablicy, przestrzeń nadal będzie wynosić nawet po przyspieszeniu, ale można to poprawić za pomocą tablicy hashtable. Lub alternatywnie możesz zapisać w tablicy z bitami z -bitowymi słowami (korzystając z obserwacji, że musisz tylko wiedzieć, czy jest pusty, czy nie; możesz znaleźć dwa znaki dla każdego podłańcucha, szukając na pierwszych dwóch pozycjach w ciągu wejściowym).O ( n log n ) F O ( n ) log nFO(nlogn)FO(n) logn

David Eppstein
źródło
Czy możesz mi powiedzieć, dlaczego uważasz, że programowanie dynamiczne będzie najlepszym wyborem dla tego problemu? Gdzie napotkamy problem, jeśli zastosujemy programowanie statyczne, takie jak C ?
tarit goswami
1
Programowanie dynamiczne to technika projektowania algorytmów, a nie klasa języków programowania.
David Eppstein