Omówienie zadania Szyld (eliminacje do IOI 2020, dzień 0)

Konwencje

W tym omówieniu będziemy oznaczać słowo będące nazwą firmy Bajtazara jako \(s\), natomiast to będące nazwą konkurencyjnej firmy jako \(t\). Zadanie można sformułować w następujący sposób: skonstruować napis, który jak największą liczbę razy zawiera napis \(s\) jako podsłowo, ale nie zawiera napisu \(t\) jako podciąg.

Dodatkowo, rozmiar alfabetu, nad którym rozważamy napisy, oznaczymy jako \(A\), a wszystkie indeksy w napisach będziemy numerować od 1.

Kiedy odpowiedź to INF?

Zauważmy, że jeżeli w słowie \(t\) występuje literka, która nie występuje w słowie \(s\), to odpowiedź w zadaniu to INF. Możemy udowodnić to w następujący sposób: ustalmy liczbę naturalną \(k\). Weźmy słowo \(r\)=\(s^k\) (\(s\) powtórzone \(k\) razy). W słowie \(r\) słowo \(s\) występuje przynajmniej \(k\) razy jako podsłowo, natomiast \(t\) nie może być podciągiem słowa \(r\), ponieważ w słowie \(r\) nie występuje pewna literka, która występuje w słowie \(t\). W takim razie możemy wybrać dowolnie duże \(k\), a więc odpowiedź to INF.

Teraz pokażmy, że jest to jedyny przypadek, w którym odpowiedź to INF. Udowodnimy to przez sprzeczność. Załóżmy, że odpowiedź to INF, ale wszystkie literki słowa \(t\) występują w słowie \(s\). Wybierzmy takie słowo \(r\), w którym znajduje się \(|t|\) parami rozłącznych wystąpień słowa \(s\) jako podsłowo (rozłączność można łatwo zapewnić, biorąc słowo \(r\), w którym jest \(|t|\cdot|s|\) wystąpień słowa \(s\) jako podsłowo). Niech \(t=t_1t_2\dots,t_{|t|}\) będą kolejnymi literami słowa \(t\). Skoro w słowie \(r\) mamy \(|t|\) parami rozłącznych wystąpień słowa \(s\), to z \(i\)-tego wystąpienia tego słowa w \(r\) możemy wybrać literkę \(t_i\) dla \(i=1,2,\dots,|t|\). W ten sposób otrzymujemy podciąg słowa \(r\), który jest równy słowu \(t\), co daje sprzeczność.

Sprawdzenie, czy wszystkie litery słowa \(t\) znajdują się w słowie \(s\) jest proste i można je zrealizować w czasie \(O(A+|s|+|t|)\) poprzez zliczanie liter w słowach \(s\) i \(t\). W dalszej części rozwiązania będziemy więc zakładać, że każda literka słowa \(t\) występuje w słowie \(s\).

Prefiksosufiksy

Prefiksosufiksem słowa \(s\) nazwiemy napis, który jest zarówno jego prefiksem jak i sufiksem. Na przykład prefiksosufiksem słowa "abacaba" jest napis "aba". Więcej o prefiksosufiksach można przeczytać w opracowaniu zadania "Szablon" z XII OI.

Zwróćmy uwagę, że jeśli w jakimś napisie mamy dwa przecinające się wystąpienia słowa \(s\) jako podsłowo, to \(s\) musi mieć prefiksosufiks o długości równej długości przecięcia tych dwóch wystąpień.

Aby lepiej zilustrować tę obserwację, rozważmy następujący przykład:

cdabcabcababbac

Widzimy, że słowo "abcab" występuje jako podsłowo w dwóch miejscach: na pozycjach 3 oraz 6. Te wystąpienia się przecinają i długość ich przecięcia jest równa 2. Oznacza to, że nasze słowo musi mieć prefiksosufiks długości 2.

Bardziej formalnie, jeśli w słowie \(r\) mamy dwa różne wystąpienia słowa \(s\) na pozycjach \(i< j\), gdzie \(j-i<|s|\), to słowo \(s\) musi mieć prefiksosufiks o długości \[ |s|-(j-i). \]

Skorzystajmy z powyższej obserwacji. Oznaczmy długość najdłuższego prefiksosufiksu właściwego (czyli niebędącego całym słowem) słowa \(s\) jako \(p\geq 0\). Widzimy, że jeżeli w pewnym słowie \(r\) mamy dwa różne wystąpienia słowa \(s\) jako podsłowo, których pierwsze literki znajdują się na pozycjach \(i< j\) w \(r\), to musi zachodzić \[ |s|-(j-i) \leq p, \] czyli równoważnie \[ j-i \geq |s|-p. \] Innymi słowy, wystąpienia słowa \(s\) jako podsłowo muszą być od siebie oddalone o przynajmniej \(|s|-p\).

Zachłanna Obserwacja

Powyższe rozważania prowadzą nas do następującej zachłannej obserwacji: załóżmy, że mamy pewne słowo \(r\), w którym słowo \(s\) występuje jako podsłowo \(k\) razy oraz \(t\) nie jest podciągiem \(r\). Wówczas istnieje słowo \(r'\), które także zawiera \(k\) wystąpień słowa \(s\) jako podsłowo, \(t\) nie jest podciągiem \(r'\) oraz kolejne wystąpienia \(s\) w \(r'\) są oddalone o dokładnie \(|s|-p\).

Dowód

Weźmy słowo \(r\) spełniające warunki z jej streści. Załóżmy, że w \(r\) mamy dwa kolejne wystąpienia słowa \(s\) jako podsłowo, których pierwsze literki znajdują się na pozycjach \(i< j\) oraz \[ j-i> |s|-p. \] Wówczas ze słowa \(r\) możemy usunąć litery znajdujące się na pozycjach od \(i+|s|-p\) do \(j-1\) (włącznie). Otrzymamy w ten sposób słowo \(r'\), o którym chcemy pokazać, że spełnia następujące warunki:

1. Słowo \(t\) nie jest podciągiem słowa \(r'\).
2. W słowie \(r'\) mamy dokładnie \(k\) wystąpień słowa \(s\) jako podsłowo.

Punkt 1. jest prosty - słowo \(r'\) powstaje z \(r\) przez usunięcie pewnej liczby liter, zatem jeśli \(t\) nie jest podciągiem \(r\), to nie może być także podciągiem \(r'\).

Zajmijmy się punktem 2. Najpierw zauważmy, że jeśli mamy pewne wystąpienie słowa \(s\) w \(r\) na pozycji \(k\geq j\), to w \(r'\) mamy wystąpienie słowa \(s\) na pozycji \(k-(j-i-|s|+p)\), ponieważ z \(r\) usunęliśmy \(j-i-|s|+p\) liter przed pozycją \(k\) i nie usunęliśmy żadnych innych.

Dalej zauważmy, że w \(r'\) mamy wystąpienie słowa \(s\) jako podsłowa na pozycji \(i\). Istotnie, literki na pozycjach od \(i\) do \(i+|s|-p-1\) w \(r'\) nie zmieniły się względem \(r\), natomiast literki na pozycjach od \(i+|s|-p\) do \(i+|s|-1\) tworzą prefiks słowa \(s\), ponieważ na pozycję \(i+|s|-p\) przechodzi wystąpienie słowa \(s\) z pozycji \(j\) w \(r\). Skoro \(s\) ma prefiksosufiks długości \(p\), to ten prefiks jest także sufiksem, a więc słowo \(s\) występuje na pozycji \(i\) w \(r'\).

Mamy stąd istotny wniosek: prefiksy słów \(r\) i \(r'\) o długości \(i+|s|-1\) są takie same. Stąd wnioskujemy, że jeśli mamy wystąpienie słowa \(s\) na pozycji \(k\) w \(r\) dla \(k < i\), to w \(r'\) mamy wystąpienie słowa \(s\) także na pozycji \(k\). Założyliśmy, że między pozycjami \(i\) oraz \(j\) w \(r\) nie ma żadnych wystąpień słowa \(s\) jako podsłowo, zatem powyższe rozumowanie pokazuje, że w \(r'\) mamy dokładnie \(k\) wystąpień słowa \(s\) jako podsłowo.

Aby zakończyć dowód pozostało zauważyć, że opisaną tu operację usuwania literek z \(r\) można wykonywać wielokrotnie. Za każdym razem sprawiamy, że pewne dwa kolejne wystąpienia słowa \(s\) jako podsłowo są od siebie oddalone o dokładnie \(|s|-p\), nie zmieniając względnego położenia innych sąsiednich par wystąpień. W ten sposób, aplikując tę operację co najwyżej \(k-1\) razy, możemy uzyskać słowo \(r'\), które spełnia wszystkie warunki z treści obserwacji.

Wniosek

Dzięki tej obserwacji, mamy następujący wniosek: niech \(k\) będzie odpowiedzią w naszym zadaniu oraz niech \(z=s[p]s[p+1]\dots s[|s|]\) będzie sufiksem słowa \(s\) o długości \(|s|-p\). Jeśli \(k\geq 1\), to w słowie postaci \(sz^{k-1}\), czyli \(s\), po którym następuje \(z\) powtórzone \(k-1\) razy, jest dokładnie \(k\) wystąpień słowa \(s\) jako podsłowo, a słowo \(t\) nie jest podciągiem tego słowa.

Rozwiązanie \(O(|s|(|s|+|t|))\)

Aby skorzystać z powyższej obserwacji, musimy najpierw sprawdzić, czy odpowiedź w naszym zadaniu jest jest równa 0. W tym celu, należy sprawdzić, czy \(t\) jest podciągiem słowa \(s\). Możemy to zrobić w czasie \(O(|s|+|t|)\) za pomocą standardowego algorytmu sprawdzającego, czy jedno słowo jest podciągiem drugiego.

Sprawdzanie czy jeden napis jest podciągiem drugiego

Będziemy przeglądać \(s\) literka po literce, utrzymując licznik \(l\) oznaczający indeks ostatniej litery słowa \(t\), która została dopasowana. Na początku algorytmu ustawiamy \(l\) na 0 i, widząc kolejną literę słowa \(s\), zwiększamy \(l\) jeśli ta litera jest ona równa literze słowa \(t\) na pozycji \(l+1\). Jeśli w którymś momencie algorytmu \(l=|t|\), to znaczy, że słowo \(t\) jest podciągiem słowa \(s\), a więc odpowiedź w zadaniu to 0. W przeciwnym przypadku odpowiedź jest dodatnia. Ten prosty algorytm jest o tyle istotny, że będzie przydatny w dalszej części rozwiązania.

Dalej założmy, że odpowiedź jest dodatnia. Możemy znaleźć długość \(p\) najdłuższego prefiksosufiksu właściwego słowa \(s\) w czasie \(O(|s|^2)\), przeglądając kolejne prefiksy i sprawdzając, czy są one prefiksosufiksami słowa \(s\). Znalazłszy \(p\), naszym zadaniem jest znalezienie największego \(k\), dla którego w słowie postaci \(sz^{k-1}\) słowo \(t\) nie jest podciągiem. W tym celu możemy zacząć od słowa \(s\) i powtarzać dodawanie sufiksu \(z\), utrzymując, tak samo jak w algorytmie sprawdzającym podciągi, licznik \(l\). Za każdym razem, gdy dodajemy kolejne wystąpienie \(z\), przeglądamy wszystkie litery słowa \(z\) i odpowiednio aktualizujemy \(l\). Jeśli po \(i\)-tym dodaniu \(z\) nastąpi stan, w którym \(l=|t|\), to znaczy, że w słowie \(sz^{i}\) słowo \(t\) jest podciągiem, a w słowie \(sz^{i-1}\) nie było, a więc odpowiedź w zadaniu to \(i\). Zauważmy, że w ten sposób nie skonstruujemy napisu dłuższego niż \(|s|+|s|\cdot |t|\), ponieważ dorzucenie każdego kolejnego \(z\) zwiększa licznik \(l\) o przynajmniej 1, skąd otrzymujemy złożoność czasową \(O(|s|(|s|+|t|))\) i pamięciową \(O(|s|+|t|)\).

Rozwiązanie \(O(|t| + |s|\cdot A)\)

Aby przyspieszyć powyższy algorytm, możemy skorzystać z algorytmu KMP do wyznaczenia nadjłuższego właściwego prefiksosufiksu słowa \(s\) w czasie \(O(|s|)\). O tym algorytmie można przeczytać w wielu miejscach, między innymi w omówieniu wspomnianego wyżej zadania "Szablon" z XII OI.

Aby uzyskać satysfakcjonującą złożoność czasową, musimy przyspieszyć jeszcze drugi krok algorytmu. Spróbujemy uzależnić złożoność od długości słowa \(t\), a nie od długości konstruowanego słowa. Zauważmy, że podczas naszego algorytmu interesuje nas jedynie, w którym miejscu w napisie \(z\) znajduje się kolejne wystąpienie litery \(t[l+1]\). W związku z tym, zamiast przeglądać wszystkie litery słowa \(z\) w kółko, możemy obliczyć tabelkę \(next[i][a]\) wymiaru \(|z|\times A\), która dla pozycji \(i\) i litery \(a\) przechowuje informację, gdzie znajduje się najbliższe wystąpienie litery \(a\) po pozycji \(i\) w słowie \(z\) lub -1, jeśli takiego wystąpienia nie ma. Tabelkę \(next\) możemy obliczyć w czasie \(O(|z|\cdot A)\), zaczynając od ostatnich pozycji i korzystając ze wzorów \[ next[i][a] = \begin{cases} -1 & \text{jeśli } i = |z|, \\ i+1 & \text{jeśli } z[i+1]=a\text{ oraz }i<|z|, \\ next[i+1][a] & \text{w przeciwnym przypadku}. \end{cases} \] Wówczas w czasie stałym możemy sprawdzić, gdzie znajduje się kolejne wystąpienie litery \(t[l+1]\) po dowolnej pozycji w napisie \(z\). W wypadku napotkania wartości -1 wracamy na początek napisu, zwiększając wynik, czyli wstawioną liczbę kopii \(z\), o 1 i tam szukamy kolejnego wystąpienia \(t[l+1]\). Trzeba być przy tym ostrożnym, gdyż powyższa definicja tabelki \(next\) nie uwzględnia wystąpień pierwszej litery słowa \(z\) - ten przypadek można sprawdzić ręcznie lub rozszerzyć tabelkę \(next\) o dodatkową "sztuczną" kolumnę \(i=0\).

Dzięki powyższym optymalizacjom, uzyskujemy złożoność czasową \(O(|t|+|s|\cdot A)\) oraz pamięciową \(O(|t|+|s|\cdot A)\). Nie było to jednak wystarczające, aby uzyskać komplet punktów na zawodach ze względu na niewielki limit pamięciowy równy 32MB.

Rozwiązanie \(O(|s|+|t|\log |s|)\)

Aby zoptymalizować zużycie pamięci poprzedniego rozwiązania, dla każdej litery zamiast tabelki \(next\) będziemy przechowywać posortowaną listę pozycji, na których ta litera występuje w słowie \(z\). Wówczas znalezienie kolejnego wystąpienia litery \(t[l+1]\) po pozycji \(i\) w \(z\) sprowadza się do znalezienia najmniejszej pozycji w tej liście większej od \(i\), co możemy zrobić w czasie \(O(\log |s|)\) za pomocą wyszukiwania binarnego.

Widzimy, że przy tym rozwiązaniu sumaryczna długość wszystkich trzymanych list to |s|, co daje dużą poprawę pod kątem zużytej pamięci względem poprzedniego pomysłu. Dzięki tej optymalizacji uzyskujemy złożoność czasową \(O(|s|+|t|\log |s|)\) oraz pamięciową \(O(|t|+|s|)\), co było wystarczające do uzyskania pełnej liczby punktów na zawodach.