Słowa Fibonacciego

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 $F_{0}=a$$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?

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 ) $F(i,j)$$i$$j$$F(i-2,j)$$F(i-1,j+\operatorname{fib}(i))$$O(n \log n)$$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 $O(n/\operatorname{fib}(i))$$F(i-2,j)$$F(i-2,j)$$F(i,j)$$O(n)$$i$$i-2$$i$

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 $F$$O(n \log n)$$F$$O(n)$ $\log n$