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 b
Znam rozwiązanie w czasie kwadratowym, ale nie mogę zredukować go do liniowego. Czy ktoś może wskazać mi właściwy kierunek?
Odpowiedzi:
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 ) ifa( i , j ) ja jot fa( i - 2 , j ) fa( i - 1 , j + fib( i ) ) O ( n logn ) ja
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 ) ) fa( i - 2 , j ) fa( i - 2 , j ) fa( i , j ) O ( n ) ja i - 2 ja
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 nF O(nlogn) F O(n) logn
źródło