Minimum Window Substring

Ustal miejsce początku podciągu. Następnie powiększaj go po jednym znaku, zliczając wystąpienia każdego znaku wewnątrz, a po każdym kroku sprawdzaj, czy obejmuje t: dla każdej z u różnych liter użytych w t okno musi zawierać co najmniej tyle ich wystąpień, ile zawiera ich t. Pierwszy koniec, który spełnia ten warunek, wyznacza najkrótsze okno obejmujące t dla tego początku, ponieważ każde krótsze okno o tym samym początku zostało wcześniej sprawdzone i nie spełniło warunku. Zatrzymaj się w tym miejscu.

Powtórz to dla każdego początku i zachowaj najkrótsze okno. Początki są sprawdzane od lewej do prawej, a okno zastępuje dotychczas najlepsze tylko wtedy, gdy jest ściśle krótsze, więc spośród okien o tej samej długości pozostaje to najbardziej z lewej.

To powolne, gdy okna są długie lub nie istnieją. Jeśli jedyne Z w s znajduje się na samym końcu, a t wymaga jednego, każdy początek wymaga odczytania aż do końca: około n²/2 kroków, czyli 1.25 × 10^9 dla n = 5 × 10^4, z których każdy obejmuje sprawdzenie maksymalnie 52 liter. To samo dzieje się, gdy żadne okno nie istnieje.

Dwa fakty pozwalają uniknąć ponownego rozpoczynania. Dodawanie znaków do okna, które zawiera t, sprawia, że nadal je zawiera, a usuwanie znaków z okna, w którym czegoś brakuje, sprawia, że nadal tego brakuje. Dlatego gdy początek przesuwa się w prawo, koniec najkrótszego okna zawierającego t może pozostać na miejscu lub przesunąć się w prawo. Oba końce mogą przesuwać się naprzód razem i żaden z nich nigdy się nie cofa.

Przesuwaj right po s, dodając każdy znak do tabeli zliczeń. Gdy tylko okno zawiera t, jest kandydatem: zapisz je, jeśli jest krótsze od najlepszego, a następnie usuń s[left], przesuń left do przodu i sprawdź ponownie. Powtarzaj, aż okno przestanie zawierać t, a potem wróć do powiększania go z prawej strony.

Żadne okno nie zostanie pominięte. Weź najlepsze okno, od L do R. Gdyby left minęło L, zanim right dotarło do R, jakieś okno zaczynające się w L i kończące przed R zawierałoby t, a byłoby krótsze od najlepszego. Zatem gdy right dociera do R, pętla zmniejszająca przesuwa left do L i zapisuje najlepsze okno. Każdy koniec przesuwa się najwyżej n razy, ale każde sprawdzenie odczytuje do u zliczeń, po jednym dla każdej litery użytej w t, mimo że od poprzedniego sprawdzenia zmieniło się tylko jedno zliczenie.

Pozostaw to samo okno i zastąp sprawdzanie jedną liczbą. Niech need[c] oznacza liczbę wystąpień c, o które prosi t, pomniejszoną o liczbę wystąpień w oknie. Wartość dodatnia oznacza, że w oknie wciąż czegoś brakuje, a ujemna — że są w nim nadmiarowe kopie. Niech missing oznacza łączną liczbę kopii, których brakuje w oknie; początkowo jest równa długości t. Okno zawiera dokładnie t, gdy missing wynosi 0.

Aktualizacja kosztuje jeden krok. Gdy s[right] trafia do okna, a jego wartość need jest większa od 0, uzupełnia brak, więc missing zmniejsza się o jeden; tak czy inaczej need zmniejsza się o jeden i może spaść poniżej 0, oznaczając nadmiarową kopię. Gdy s[left] opuszcza okno, need zwiększa się o jeden, a jeśli teraz jest większa od 0, okno oddało kopię potrzebną w t, więc missing zwiększa się o jeden. Nadmiarowe kopie pojawiają się i znikają bez wpływu na missing.

Prześledźmy s = banana, t = aan: początkowo need wynosi 2 dla a i 1 dla n, a missing wynosi 3. b nie jest potrzebne. Pierwsze a zmniejsza missing do 2, n do 1, a drugie a do 0, więc bana zawiera t. Zmniejszanie okna usuwa nadmiarowe b i pozostawia ana — trzy znaki, czyli nowe najlepsze okno. Usunięcie tego a przywraca missing do 1. Ostatnie a ponownie daje komplet, tym razem w nana, które zmniejsza się do drugiego ana. Nie jest ono krótsze, więc pozostaje pierwsze, najbardziej z lewej strony ana.

Każdy znak s wchodzi do okna raz i opuszcza je najwyżej raz, a każdy ruch wymaga stałej ilości pracy. Tworzenie need wymaga jednokrotnego odczytania t. Całe działanie ma złożoność O(n + m), a jedyną dodatkową pamięcią jest tablica 128 liczników.