Informatyka MIMUW

Niech \( S[i] \) będzie rozmiarem minimalnego pokrywającego słowa dla prefiksu \( x[1..i] \). Poprawność wynika z następującego faktu: \ \( S[i]=i \ \textrm{lub}\ S[i]=S[P[i]]. \)

Wystarczy wykazać, że
\( P'[i]=j,\ P'[j]=k>0\ \Rightarrow \ i\ge k+j \)
Fakt ten wynika z lematu o okresowości i z definicji tablicy P'.

Słowa Fibonacciego definiujemy następująco:
\( F_0=a,\ F_1=ab,\ F_{n+1}\ =\ F_n\cdot F_{n-1} \)
Na przykład: \( F_3=abaab,\ F_4=abaababa,\ F_5=abaababaabaab. \)
Niech \( F'_n \) oznacza słowo Fibonacciego z obciętymi ostatnimi dwoma symbolami. Jeśli jako wzorzec weźmiemy słowo Fibonacciego \( F_n \), a jako tekst słowo \( F'_ncc \) to przy wczytywaniu \( |F_n-1| \)-ego symbolu algorytm ma opóżnienie logarytmiczne, iterujemy \( \Omega(\log n) \) razy operację: \( j:=P'[j] \).

Weźmy graf, którego węzłami są litery, a słowa wejściowe odpowiadają krawędziom. Wystarczy znalezć minimalną liczbę krawędzi, które trzeba dołożyć do grafu, by miał on ścieżkę Eulera.

Dygresja Zadanie to było na Olimpiadzie Informatycznej pod nazwą pierwotek abstrakcyjny. Ciekawe jest to, że problem robi się NP-zupełny, gdy wszytkie słowa wejściowe mają długość 3.

Lemat ten wynika z poprawności algorytmu Euklidesa z odejmowaniem, który oblicza nwd(p,q). Zauważmy, że jeśli \( p>q \) są okresami, to p-q też jest okresem.

Indukcja ze względu na p+q.

Problem jaki musimy rozwiązać to właściwość algorytmu, którą nazwiemy opóżnieniem. Polega ona na tym, że w danym kroku algorytm może wciąż jeszcze rozważać właściwy prefiks aktualnego słowa i nie dotrzeć w ogóle do rozważenia bieżącej litery. Pokażemy jednak, że w momencie, kiedy nastąpi wystąpienie wzorca, kolejka zostanie opróżniona, co wystarczy do dowodu poprawności algorytmu.
Dowód przeprowadzimy nie wprost - załóżmy, że w tym kroku kolejka się nie opróżni i że jest to pierwsze wystąpienie wzorca, którego algorytm nie zdąża wyśledzić. Zacznijmy rozważanie działania algorytmu od ostatniego miejsca wcześniejszego od bieżącego, w którym kolejka się opróżnia. W tym momencie zachodzi \( j < m \) (nawet jeżeli w owym kroku było wystąpienie wzorca w tekście, to ten warunek i tak będzie po tym kroku spełniony) oraz \( |Kolejka|=0 \). Pokażemy, że odtąd aż do miejsca wystąpienia wzorca zachodzić będzie niezmiennik
\( |Kolejka| < m-j. \)
Faktycznie, zastanówmy się co się może wydarzyć w dowolnym, kolejnym kroku algorytmu, a co może zmienić wartość zmiennej \( j \):
Może być dwukrotnie wywołana instrukcja \( j:=P[j] \). Wówczas \( |Kolejka| \) wzrasta o \( 1 \), \( m-j \) wzrasta co najmniej o \( 2 \), czyli niezmiennik dalej zachodzi.
Moze być raz wywołana instrukcja \( j:=P[j] \), a raz \( j:=j+1 \) (w jakiejkolwiek kolejności). Wówczas \( |Kolejka| \) się nie zmienia, \( m-j \) pozostaje bez zmian lub wzrasta, co nie zaburza niezmiennika.
Mogą nastąpić dwie instrukcje powiększające \( j \) o \( 1 \). Wówczas \( |Kolejka| \) maleje o \( 2 \), \( m-j \) także maleje o \( 2 \), zatem niezmiennik pozostaje zachowany.


Kolejka \textit{nie} może się opróżnić, gdyż zakładamy, że to nie nastąpi przed aktualnie rozważanym wystąpieniem wzorca. Instrukcja \( j:=P[m] \) również nie może wystąpić, ponieważ oznaczałoby to wcześniejsze od rozważanego niezauważone przez algorytm wystąpienie wzorca w tekście.

Zatem niezmiennik jest zachowany od ostatniego momentu opróżnienia kolejki do momentu niezauważonego wystąpienia wzorca. W chwili przetworzenia literki, która powoduje wystąpienie zachodzi \( j=m \), czyli na mocy pokazanego niezmiennika \( |Kolejka| < m-m=0 \), \( |Kolejka| < 0 \). To z kolei daje żądaną sprzeczność.

(Rozwiązanie opracował Jakub Radoszewski)

By wykazać, że algorytm Oszczędny-MP wykonuje co najwyżej \( \frac{3}{2}n \) porównań, pogrupujemy te porównania w dwie szufladki: \( A \) i \( B \) . Pokażemy, że w szufladce \( A \) będzie co najwyżej \( n \) porównań, a w szufladce \( B \) co najwyżej \( \frac{n}{2} \) porównań. Do szufladki \( A \) wrzucamy:

Wszystkie udane porównania dokonane w trakcie szukania wzorca \( x' \) .

Wszystkie nieudane porównania pierwszej litery wzorca \( x' \) (czyli litery \( b \) ), dokonane w trakcie szukania wzorca \( x' \) .

Wszystkie porównania początkowych liter \( a \) , za wyjątkiem porównań na tych pozycjach, gdzie wcześniej szukaliśmy litery \( b \) (pierwszej litery wzorca \( x' \)) i nie znaleźliśmy jej.

Do szufladki \( B \) wrzucamy wszystkie pozostałe porównania, czyli:

Wszystkie nieudane porównania dokonane w trakcie szukania wzorca \( x' \) , za wyjątkiem nieudanych porównań pierwszej litery; są to nieudane porównania dokonywane w momencie, gdy znaleźliśmy już jakiś niepusty prefiks \( x' \) .

Porównania początkowych liter \( a \) na tych pozycjach, gdzie wcześniej szukaliśmy litery \( b \) i nie znaleźliśmy jej.

Zauważmy, że w algorytmie MP pozycje tekstu, na których nigdy nie było żadnego udanego porównania to dokładnie te pozycje, na których nie udało się znaleźć pierwszej litery wzorca (lub pozycja jest pod sam koniec tekstu i nie ma już szans na znalezienie wzorca, algorytm już się zakończył). Dodatkowo, zarówno algorytm MP jak i algorytm Oszczędny-MP ma taką właściwość, że jeśli na pewnej pozycji tekstu było udane porównanie, to ta pozycja tekstu już nigdy nie będzie porównywana (o niej ,,wiemy już wszystko). W związku z tym każde porównanie z szufladki \( A \) wykonuje się na innej literze tekstu, czyli tych porównań jest co najwyżej \( n \) .
Spójrzmy teraz, jak zmienia się wskaźnik, na jakiej pozycji szukamy teraz wzorca \( x \) . Zauważmy, że prefikso-sufiks słowa \( x[1\ldots s] \) dla \( s > k \) jest długości co najwyżej \( s - k - 1 \) (litery \( a \) tego prefikso-sufiksu muszą się zaczynać za literą \( b \) na pozycji \( k+1 \) ). W związku z tym w momencie nieudanego porównania, które wystąpiło gdy znaleziony już został niepusty prefiks słowa \( x' \) , wskaźnik ,,gdzie teraz szukamy przesuwa się o conajmniej \( k+1 \) . Tak też jest, gdy znajdziemy całe słowo \( x' \) ( przesuwamy się do prefikso-sufiksu słowa \( x \)) . Dodatkowo, każde nieudane porównanie litery \( b \) z pozycji \( k+1 \) w słowie \( x \) przesuwa wskaźnik o jeden.
W związku z tym:
Porównania z szufladki \( B \) , podpunkt \( 1 \) przesuwają wskaźnik o conajmniej \( k+1 \geq 2 \) .

Po co najwyżej \( k \) porównaniach z szufladki \( B \) , podpunkt \( 2 \) wskaźnik przesunie się o conajmniej \( k+1 \) . Dodatkowo, każde takie porównanie oznacza, że wcześniej na tym miejscu było nieudane porównanie litery \( b \) . Wliczając przesunięcia pochodzące od tych porównań otrzymujemy, że wskaźnik przesunął się o conajmniej \( k+1+L \geq 2L \) , gdzie \( L \) to liczba takich porównań liter \( a \) w jednej próbie znalezienia wzorca \( x \) .

Czyli każde porównanie z szufladki \( B \) przesuwa aktualny wskaźnik (gdzie teraz szukamy) o conajmniej \( 2 \) , czyli tych porównań jest nie więcej niż \( \frac{n}{2} \) .
(Rozwiązanie opracował Marcin Pilipczuk)

Zadanie ma to związek z pewną metodą konstrukcji cyklu Eulera, chociaż zadanie pozornie wydaje się nie mieć nic wspólnego z grafami. Mamy tu do czynienia z grafem ktorego węzłami są wszystkie słowa binarne długości n-1.
Istnieje krawędż u \rightarrow v o etykieci a, gdy Append(Cutfirst(u),a)=v.
Ciąg operacji w algorytmie Słowa-Cykliczne odpowiada zachłannej ścieżce Eulera która startuje z węzła \( 1^{n-1} \). patrz zadania w module Algorytmy grafowe.