Rozważmy szczególny problem wyszukiwania skompresowanego wzorca: prawdziwy wzorzec jest długości wykładniczej, ale można go zapisać jako ciąg numerów słów Fibonacciego, których konkatenacja daje wzorzec. Jest to bardzo szczególna i prosta sytuacja. Co więcej wzorca szukamy tylko wewnątrz słów Fibonacciego.
Szukanie konkatenacji słów Fibonacciego w słowach Fibonacciego
Niech \(h\) będzie funkcją określoną na napisach złożonych z cyfr 0 i 1. Funkcja \(h\) przekształca napis \(w\), zastępując (niezależnie i równocześnie) każdą cyfrę 0 przez 1 i każdą cyfrę 1 przez napis "10". Na przykład \(h(\)1001\() =\) 101110, \(h( \emptyset ) = \emptyset\) (tzn. funkcja \(h\) zastosowana do pustego napisu jest pustym napisem). Zauważmy, że \(h\) jest różnowartościowa. Przez \(h^k\) oznaczmy \(k\)-krotne złożenie funkcji \(h\) ze sobą. W szczególności, \(h^0\) to funkcja identycznościowa \(h^0(w) = w\).
Interesują nas napisy postaci \(h^k(\)0\()\) dla \(k = 0,\, 1,\, 2,\, 3,\dots\). Oto kilka pierwszych takich napisów:
- 0
- 1
- 10
- 101
- 10110
- 10110101
Mówimy, że napis \(x\) jest podsłowem napisu \(y\), jeżeli występuje w nim jako spójny (tj. jednokawałkowy) podciąg. Mamy dany ciąg liczb naturalnych \(k_1,\, k_2,\ldots,\, k_n\). Celem zadania jest sprawdzenie, czy napis postaci
$$h^{k_1}(\mathtt{0}) \cdot h^{k_2}(\mathtt{0}) \cdots h^{k_n}(\mathtt{0})$$
jest podsłowem \(h^m(\)0\()\) dla pewnego \(m\).
Rozwiązanie algorytmiczne
Dla wygody wprowadźmy oznaczenie \(h_k := h^k(\)0\()\). Słowa \(h_k\) są to tzw. słowa Fibonacciego. Zazwyczaj definiuje się je rekurencyjnie w następujący sposób:
$$h_0 = \mathtt{0}, \quad h_1 = \mathtt{1}, \quad h_k = h_{k-1} h_{k-2} \quad \text{dla } k \ge 2 \qquad (*)$$
Równoważność definicji \((*)\) i tej podanej w treści zadania łatwo pokazać przez indukcję. Rozwiązanie wzorcowe bazuje na definicji przez podstawienie, którą podano w treści zadania. Postać \((*)\) może być jednak pomocna w zrozumieniu niektórych własności, z których będziemy korzystać.
Powiemy, że ciąg \((k_1,\ldots,\, k_n)\) jest dobry, jeżeli \(h_{k_1} \ldots h_{k_n}\) jest podsłowem \(h_m\) dla pewnego \(m\), oraz że jest zły w przeciwnym przypadku. Zadanie polega więc na sprawdzeniu, czy dany na wejściu ciąg \((k_1,\ldots,\, k_n)\) jest dobry.
Pierwsze podejście do rozwiązania tego zadania może wyglądać następująco: generujemy całe słowo \(h_{k_1} \ldots h_{k_n}\), po czym sprawdzamy za pomocą algorytmu wyszukiwania wzorca (np. KMP), czy występuje ono jako podsłowo w \(h_m\) dla odpowiednio dobranego \(m\). Okazuje się, że jeżeli \(h_m\) jest co najmniej \(8\) razy dłuższe niż wyszukiwane słowo, to rozwiązanie takie działa poprawnie. Jednakże już pobieżna analiza pozwala stwierdzić, że takie rozwiązanie nie ma szans powodzenia na już średniego rozmiaru danych wejściowych, gdyż rozmiar słowa \(h_k\) rośnie wykładniczo względem \(k\). Dlatego rozwiązanie, którego szukamy, musi operować tylko na ciągu \((k_1,\ldots,\, k_n)\), bez generowania słowa, które ten ciąg reprezentuje.
Idea rozwiązania wzorcowego polega na przekształcaniu danego ciągu \(w = (k_1,\ldots,\, k_n)\) przez coś w rodzaju funkcji odwrotnej do \(h\). Okazuje się, że dla dużych wyrazów ciągu \(w\) cofanie funkcji \(h\) polega na zwykłym ich zmniejszaniu, a dla małych (nie większych niż \(3\)) trzeba czasem rozpatrywać pewne przypadki szczególne. Operacje, które wykonuje algorytm, mają tę własność, że ciąg dobry przekształcają w ciąg dobry, a zły - w zły. Proces ten doprowadza w końcu do ciągu jednowyrazowego, który oczywiście jest dobry (wtedy ciąg początkowy też był dobry), lub do ciągu, o którym potrafimy stwierdzić, że na pewno jest zły (wtedy początkowy był zły).
Złożoność
Zanim przystąpimy do dowodu poprawności przedstawionego rozwiązania, zastanówmy się nad czasem jego działania. W szczególności upewnijmy się, że algorytm ten się w ogóle zatrzymuje. Pokażemy, że czas działania algorytmu na ciągu \((k_1,\ldots,\, k_n)\) wynosi \(O(k_1 + \ldots + k_n + n)\). Przyjrzyjmy się pojedynczej iteracji pętli while.
Niech \(n\) oznacza bieżącą długość ciągu \(w\), a \(s\) - bieżącą sumę wyrazów ciągu \(w\) z pominięciem pierwszego, jeżeli jest mniejszy od \(2\). Pokażemy, że po wykonaniu instrukcji z głównej pętli programu wartość \(s + n\) maleje o co najmniej \(\lfloor \frac{n}{2} \rfloor\). Faktycznie, początkowe \(0\) lub \(1\) nie zmienia wartości \(s + n\), gdyż nie jest uwzględnione w jej obliczeniu. Inne zmiany, czyli:
- końcowe \(3\) przechodzi w \(1\),
- końcowe \(1\) znika,
- fragment \(1,\, 0\) przechodzi w \(1\),
- fragment \(3,\, 0\) przechodzi w \(1,\, 1\),
- pozostałe wyrazy zmniejszają się o \(1\),
powodują zmniejszenie wartości \(s + n\) o co najmniej \(1\) dla każdego wyrazu lub każdej pary kolejnych wyrazów ciągu \(w\). Wynika stąd, że \(s + n\) maleje łącznie o co najmniej \(\lfloor\frac{n}{2}\rfloor\). Oczywiście jeżeli \(s + n \leq 1\), algorytm się zatrzymuje. Jako że czas wykonania pojedynczej iteracji pętli while wynosi \(O(n)\), jest on w pełni amortyzowany przez zmianę \(s + n\). Zatem całkowity czas działania algorytmu wynosi \(O(s + n)\).
Kilka prostych własności słów \(h_k\)
Potrzebujemy kilku prostych obserwacji o słowach \(h_k\). W przekształceniu \(h(h_{k-1}) = h_k\) każda cyfra 0 w \(h_k\) powstaje w wyniku podstawienia 1 \(\to\) 10, a każda cyfra 1, po której nie występuje 0 - w wyniku podstawienia 0 \(\to\) 1. Wynika stąd w szczególności, że:
- \(h_k\) zaczyna się od 1 dla \(k \geq 1\),
- \(h_k\) kończy się na 0 dla \(k\) parzystych, a na \(1\) dla \(k\) nieparzystych,
- w \(h_k\) nie występuje podsłowo 00,
- w \(h_k\) nie występuje podsłowo 111 (jest to wniosek z (c) dla słowa \(h_{k-1}\),
- w \(h_k\) nie występuje podsłowo 101010 (jest to wniosek z (d) dla słowa \(h_{k-1}\)).
Poprawność odpowiedzi false
Uzasadnimy, że kryterium, które odrzuca ciąg \(w\) jako zły, jest poprawne.
Fakt
Jeżeli \(k \notin \lbrace 1,\, 3 \rbrace\), to \(h_k\)0 nie jest podsłowem żadnego \(h_m\).
Jeżeli \(k\) jest parzyste, \(h_k\) kończy się cyfrą 0. Wtedy \(h_k\)0 ma sufiks 00, który nie może być podsłowem żadnego \(h_m\). Jeżeli \(k\) jest nieparzyste i \(k \geq 5\), to można udowodnić (np. korzystając z postaci \((*)\)), że słowo \(h_k\) ma sufiks \(h_5 = \) 10110101, a więc także 10101, czyli 101010 jest sufiksem słowa \(h_k\)0. Ale zgodnie z punktem (e) powyżej, słowo 101010 nie może wystąpić w żadnym \(h_m\). Dowodzi to poprawności faktu.
Poprawność odpowiedzi true
Teraz uzasadnimy, że każda z operacji wykonywanych głównej pętli programu jest poprawna, tzn. że ciąg \(w\) jest dobry po wykonaniu tej operacji wtedy i tylko wtedy, gdy był dobry przed jej wykonaniem. Zauważmy przy tym, że wszystkie operacje poza ostatnią (zmniejszenie wartości wyrazów ciągu o \(1\)) są od siebie niezależne i mogą być wykonane w dowolnej kolejności. Dla ciągu \(w = (k_1,\ldots,\, k_n)\) wprowadzamy oznaczenie \(h_w = h_{k_1} \ldots h_{k_n}\).
Jeżeli w ciągu \(w\), poza pierwszym wyrazem, występuje jakiekolwiek \(0\), to musi być ono poprzedzone przez \(1\) albo \(3\), gdyż w przeciwnym przypadku ciąg \(w\) zostałby odrzucony przy wcześniejszym sprawdzeniu. Ponieważ \(h_1 h_0 =\) 10 \(= h_2\) i \(h_3 h_0 =\) 1010 \(= h_2 h_2\), instrukcje zamiany \(1,\, 0 \to 2\) i \(3,\, 0 \to 2,\, 2\) przekształcają ciąg \(w\) w równoważny ciąg \(w'\), taki że \(h_w = h_{w'}\). To dowodzi, że operacje te są poprawne, ponadto eliminują one wszystkie zera występujące w \(w\) poza być może pierwszym.
Aby pozbyć się początkowego zera zauważmy, że jeżeli \(h_w\) występuje jako podsłowo w \(h_m\), to początkowe zero musi być drugą cyfrą fragmentu 10 \(= h_2\). Oznacza to, że jeżeli na początku ciągu \(w\) zamienimy \(0\) na \(2\), to dla tak otrzymanego \(w'\) słowo \(h_{w'}\) również występuje jako podsłowo w \(h_m\). To dowodzi poprawności operacji \(0 \to 2\).
Uzasadnimy teraz poprawność instrukcji \(3 \to 2\), usunięcia końcowej jedynki i obniżenia wartości wszystkich wyrazów ciągu o \(1\). Załóżmy, że w ciągu \(w\) nie występuje żadne zero. Oznaczmy przez \(w'\) ciąg, który powstaje z \(w\) po zastosowaniu operacji \(3 \to 2\) i usunięcia końcowej jedynki. Operacje te odcinają ostatnią cyfrę \(1\) z \(h_w\), jeżeli ciąg \(w\) kończy się na \(1\) lub \(3\). Zatem \(h_w = h_{w'}\) lub \(h_w = h_{w'}\)1, przy czym w tym pierwszym przypadku ciąg \(w'\) nie kończy się na \(1\) ani na \(3\). Oznaczmy przez \(w''\) ciąg, który powstaje z \(w'\) przez zmniejszenie wszystkich wyrazów o \(1\).
Najpierw udowodnimy, że jeżeli \(w\) jest dobry, to \(w''\) także jest dobry. Załóżmy, że \(h_w\) jest podsłowem \(h_m\) i zastanówmy się, z czego powstaje to podsłowo w przekształceniu \(h(h_{m-1}) = h_{m}\). Niech \(w' = (k_1,\ldots,\, k_n)\). Pokażemy, że dla każdego \(i\) odpowiedni człon \(h_{k_i}\) w \(h_w = h_{k_1} \ldots h_{k_n}\) powstaje dokładnie z \(h_{k_i-1}\). Funkcja \(h\) jest różnowartościowa, a zatem nie istnieje żadne inne słowo \(x\), takie że \(h(x) = h_{k_i}\). Jeśli więc \(h_{k_i}\) nie powstaje z \(h_{k_i-1}\), to przekształcenie \(h(h_{m-1}) = h_m\) zamienia pewną cyfrę 1 w blok 10, który występuje na granicy wystąpienia \(h_{k_i}\) w \(h_m\), tzn. prawe 0 jest pierwszą cyfrą \(h_{k_i}\) lub lewe 1 jest ostatnią cyfrą \(h_{k_i}\). Ten pierwszy przypadek jest niemożliwy, bo \(h_{k_i}\) zaczyna się od 1.
Drugi przypadek może zajść jedynie wtedy, gdy po \(h_{k_i}\) występuje 0. Tak nie jest dla \(i < n\) (wówczas po \(h_{k_i}\) występuje \(h_{k_{i+1}}\)), ani dla \(i = n\) w przypadku, gdy \(h_w = h_{w'}\)1. Zatem musi być \(i = n\) oraz \(h_w = h_{w'}\), ale wtedy \(k_i \notin \lbrace 1,\, 3 \rbrace\), więc otrzymujemy sprzeczność.
Tym samym pokazaliśmy, że fragment \(h_{k_1} \ldots h_{k_n}\) w \(h_w\) jako podsłowie \(h_m\) powstaje w wyniku zastosowania przekształcenia \(h\) do \(h_{k_1-1} \ldots h_{k_n-1} = h_{w''}\). Zatem \(h_{w''}\) jest podsłowem \(h_{m-1}\), czyli \(w''\) jest dobry.
Pozostała do wykazania implikacja w drugą stronę. Jeżeli \(w''\) jest dobry, to istnieje takie \(m\), że \(h_{w''}\)0 lub \(h_{w''}\)1 jest podsłowem \(h_m\). Stąd \(h(h_{w''}\mathtt{0}) = h_{w'}\mathtt{1}\) lub \(h(h_{w''}\mathtt{1}) = h_{w'}\mathtt{10}\) jest podsłowem \(h_{m+1}\), a jedno i drugie zaczyna się od \(h_w\). Zatem \(w\) jest dobry.