Omówienie zadania Szablon 2 (III etap XXIX OI)

Zauważmy, że aby szablon lub jego odwrócenie pokryło pierwszą literę słowa \(s\), musi pokryć cały prefiks słowa. Jeśli jakieś słowo jest prawidłowym szablonem, to również jego odwrócenie, wobec tego wystarczy ograniczyć się do kandydatów na szablony, które są prefiksami naszego słowa. Wynika z tego, że dla każdej długości szablonu mamy tylko jednego kandydata. Będziemy sprawdzać kolejno \(n\) kandydatów o coraz większych długościach.

Podzadania 1 i 2

Możemy zrobić sprawdzenie danego kandydata długości \(L\), zaznaczając wszystkie pozycje, na których zaczynają się pokrycia szablonem lub jego odwróceniem oraz dodatkowo pozycję za ostatnią literą słowa, a następnie sprawdzając, czy maksymalna odległość pomiędzy dwoma zaznaczonymi pozycjami jest nie większa niż \(L\). Jeżeli tak, to znaleźliśmy prawidłową długość szablonu.

Jeżeli na każdej z \(n\) pozycji będziemy sprawdzać pokrycie brutalnie (czyli w czasie liniowym), to uzyskamy rozwiązanie działające w czasie \(O(n^3)\).

Jeśli wykorzystamy do tego np. haszowanie (czyli sprawdzamy w czasie stałym), to uzyskamy rozwiązanie o złożoności \(O(n^2)\).

Podzadanie 3

W rozwiązaniu będziemy korzystać z funkcji \(pref\), która dla każdej pozycji w słowie \(s\) mówi nam, jak długi prefiks całego słowa zaczyna się na tej pozycji. Istnieje standardowy algorytm wyznaczania tablicy \(pref\) w czasie \(O(n)\) (bardzo podobny do algorytmu Manachera), ale nam wystarczy obliczenie tej tablicy w czasie \(O(n \log n)\), używając haszowania i wyszukiwania binarnego.

Dzięki tej tablicy możemy łatwo stwierdzić, czy można przyłożyć szablon na danej pozycji. Jeżeli szablon ma długość \(L\), to możemy go przyłożyć na pozycji \(i\), wtedy gdy \(pref[i] \geq L\). Przyda nam się również odwrócona funkcja \(pref_R\), która mówi, jak długi odwrócony prefiks słowa może kończyć się na danej pozycji. Odwrócony szablon długości \(L\) można zakończyć na pozycji \(i\), jeśli \(pref_R[i] \geq L\). Zatem za pomocą tych dwóch funkcji możemy łatwo znaleźć miejsca, w których pokrywamy słowo szablonem (pokrycie fragmentu \(s[i .. i+L-1]\)) i jego odwróceniem (pokrycie fragmentu \(s[i-L+1 .. i]\)).

Funkcję \(pref_r\) można łatwo wyznaczyć, obliczając standardową funkcję \(pref\) dla naszego słowa z doklejonym jego odwróceniem: \(ss^R\). Jeżeli tablica \(pref\) powie nam, że w odwróconej części słowa na pozycji \(i\) mamy jakiś prefiks \(p\), to znaczy, że na pozycji \(2n + 1 - i\) w oryginalnym słowie kończy się wystąpienie odwróconego prefiksu. Dzięki temu obliczymy wartość funkcji \(pref_r\) dla tej pozycji.

Jesteśmy już gotowi do sprawdzania, czy prefiks długości \(L\) jest szablonem pokrywającym całe słowo. Przyspieszymy w tym celu poprzednie rozwiązanie.

Zauważmy, że jeżeli przechodzimy z kandydata długości \(L\) na kandydata długości \(L + 1\), to nie musimy od początku wyznaczać pozycji, na których zaczepione są pokrycia. Dla każdej pozycji, w której zaczyna się pokrycie normalnym słowem, od pewnego momentu to pokrycie już nie będzie zaczynać się na tej pozycji. Wobec tego te pozycje możemy trzymać na secie (strukturze danych set) i w odpowiednim momencie usuwać. Każda pozycja zostanie usunięta tylko raz.

Problematyczne są pozycje dla pokryć słowem odwróconym, ponieważ przy zwiększaniu długości kandydata musimy przesunąć początki tych pokryć w lewo. Pomysł jest więc taki, żeby dla odwróconych pokryć trzymać na drugim secie pozycje ich prawych końców i również usuwać je w odpowiednim momencie. Obsługę tych setów możemy zrobić w sumarycznym czasie \(O(n \log n)\). I dla każdego kandydata \(L\) wiemy, że na secie znajdują się jego pozycje.

Możemy spróbować zachłannie sprawdzić, czy te pozycje odpowiadają poprawnemu pokryciu. Jeżeli startujemy z pozycji \(1\), to wiemy, że mamy pokrycie aż do pozycji \(L\). Czyli teraz chcielibyśmy na naszym secie znaleźć największą pozycję, nie większą niż \(L + 1\). Jeżeli ta pozycja będzie większa niż \(1\), to znaczy, że możemy rozszerzyć nasze pokrycie do pozycji \(i\), zatem dalej szukamy pokrycia od pozycji \(i + L\). Czyli znowu na secie znajdujemy największą pozycję, nie większą niż \(i + L\), albo gdybyśmy chcieli skorzystać tutaj z seta odwróconego, to na nim znajdujemy największą pozycję, nie większą niż \(i + 2L - 1\).

Okazuje się, że jeżeli w ten zachłanny sposób będziemy tworzyć pokrycie dla kandydata długości \(L\), to będzie ono miało nie więcej niż \(\frac{2n}{L}\) elementów. Jest tak dlatego, że jeżeli rozważymy sobie trzy kolejne elementy pokrycia, to pierwszy i trzeci muszą być rozłączne. Gdyby bowiem nie były rozłączne, to mielibyśmy sprzeczność, ponieważ w rozwiązaniu zachłannym drugi element nie mógłby być wybrany, ponieważ pozycja trzeciego elementu jest większa, a nadal rozszerza pokrycie generowane przez pierwszy element. Wynika z tego, że jeżeli posumujemy sobie długości pokryć dla wszystkich kandydatów, to będzie to co najwyżej \[\sum_L \frac{2n}{L} = O(n \log n).\]

Tak więc jeżeli uwzględnimy, że przy wyznaczaniu kolejnego elementu pokrycia musimy wykonać funkcję lower_bound w dwóch setach, to dostaniemy, że całkowita złożoność programu to \(O(n \log^2 n)\).

Rozwiązanie wzorcowe

W rozwiązaniu wzorcowym dla danej długości kandydata \(L\) trzymamy, tak jak poprzednio, miejsca, w których możemy przyłożyć szablon na dwóch setach. Ale oprócz tego trzymamy zmienną \(t\), która oznacza, jakiej minimalnej długości musiałyby być te przyłożenia szablonu, żeby dla aktualnych pozycji pokryły całe słowo. Widać, że pokrycie istnieje, gdy \(L \geq t\). Pokażemy teraz, jak można uaktualniać wartość \(t\) podczas zwiększania długości kandydata \(L\).

Gdy zwiększamy długość \(L\), część pozycji może stać się już nieaktualna i zostaną usunięte z setów; w takim przypadku wartość \(t\) może nam wzrosnąć. Pomysł jest taki, żeby te pozycje wyrzucać po kolei i po każdym wyrzuceniu sprawdzać, czy wartość \(t\) jest wystarczająco duża. Jeśli chcemy wyrzucić przyłożenie na pozycji \(i\), to musimy sprawdzić, czy pokrywany przedział \(s[i..i+L-1]\) nadal będzie pokryty.

W tym celu znajdujemy sobie poprzednika i następnika tego przyłożenia. To znaczy przyłożenie występujące bezpośrednio z lewej strony i przyłożenie występujące bezpośrednio z prawej strony. To możemy zrobić za pomocą operacji lower_bound na setach, tylko musimy oczywiście uwzględnić oba sety. Gdy mamy już te dwa przyłożenia, sprawdzamy, czy pokrywają one przedział pokrywany wcześniej przez usunięte przyłożenia.

Jeśli nie pokrywają, to aktualna wartość \(t\) jest za mała. Moglibyśmy próbować jakoś sprytnie wyznaczyć, jaka wartość będzie dobra, ale to jest kłopotliwe, jeżeli musimy rozpatrywać przyłożenia szablonu i jego odwrócenia. Zamiast tego po prostu zwiększymy \(t\) o \(1\) i wykonamy całą procedurę sprawdzenia od początku.

Jaka jest złożoność czasowa tego rozwiązania? Tak jak powiedzieliśmy wcześniej, utrzymywanie setów działa w czasie \(O(n \log n)\). Utrzymywanie wartości \(t\) również będzie działać w takim czasie: każdy test działa w czasie \(O(\log n)\), a testów będziemy mieli \(n\), ponieważ \(n\) razy będziemy usuwać jakieś przyłożenia oraz wartość \(t\) będziemy mogli zwiększyć co najwyżej \(n\) razy (nie może być ona większa niż \(n\)).

Ostatecznie zatem całe rozwiązanie będzie działało w czasie \(O(n \log n)\).