Trening z drzwiami II

Zgodnie z obietnicą wrócimy do zadania o nawiasach umieszczonych na prostokątnej planszy. Tym razem rozwiążemy je w czasie liniowym!

Przypomnijmy, że w zadaniu pracujemy z prostokątną planszą n \times m, na której polach umieszczone są nawiasy. Interesuje nas zliczenie prostokątnych fragmentów tej planszy, w których każdy wiersz to prawidłowe nawiasowanie. W poprzednim odcinku skonstruowaliśmy rozwiązanie działające w czasie \mathcal{O}(nm\min(n,m)), ale dzisiaj celujemy w złożoność \mathcal{O}(nm).

Pomyślmy jeszcze raz o przeglądaniu i-tego wiersza od prawej do lewej. Postępując tak jak poprzednio, to jest utrzymując już przetworzone kolumny na stosie, łatwo wyznaczyć nazwy \textrm{name}_i[j] o takiej własności, że t_i[c_1]t_i[c_1+1] \ldots t_i[c_2] jest prawidłowym nawiasowaniem dokładnie wtedy, gdy \textrm{name}_i[c_1-1]=\textrm{name}_i[c_2]. (Jak? Kopiując nazwę odpowiadającą wierzchołkowi stosu albo nadając całkiem świeżą nazwę.) Istotnie upraszcza to całą sytuację: teraz po ustaleniu r_1 musimy tylko dla każdych c_1 \leq c_2 policzyć najdłuższy wspólny prefiks słów \textrm{name}_{r_1}[c_1-1]\textrm{name}_{r_1+1}[c_1-1]\ldots oraz \textrm{name}_{r_1}[c_2]\textrm{name}_{r_1+1}[c_2]\ldots. Dokładnie opisuje on „dobre” wartości r_2.

Czyli całe zadanie jest z algorytmów tekstowych! Świetnie. Zauważmy, że w tym momencie jest to już tak naprawdę problem jednowymiarowy. Dzięki nadaniu nazw kolejność kolumn nie jest bowiem istotna, to znaczy możemy je dowolnie poprzestawiać. Bardziej formalnie, oznaczmy c[j] = \textrm{name}_{r_1}[j]\textrm{name}_{r_1+1}[j]\ldots. Ponieważ interesuje nas policzenie sumy \textrm{lcp}(c_{i-1},c_j) po wszystkich i \leq j, możemy posortować wszystkie słowa leksykograficznie i nie zmieni to wyniku! Jeśli dodatkowo po posortowaniu zapiszemy sobie najdłuższy wspólny prefiks między każdą parą sąsiednich słów, możemy całkiem zapomnieć o oryginalnych słowach. Jest to dokładnie ten sam trik, z którego korzysta się przy wyszukiwaniu w tablicy sufiksowej: jeśli c_0,c_1,\ldots,c_m są posortowane leksykograficznie, a \textrm{lcp}[j] oznacza najdłuższy wspólny prefiks między c_{j-1} a c_j, to najdłuższy wspólny prefiks między c_{i} a c_j, gdzie i < j jest równy minimum z \textrm{lcp}[i+1],\textrm{lcp}[i+2],\ldots,\textrm{lcp}[j]. Całą syttuację najlepiej wyobrażać sobie tak jak na poniższej ilustracji, na której kolejne wiersze odpowiadają napisom, a czerwone kreski symbolizują najdłuższe wspólne prefiksy między parami sąsiadów. Patrząc na rysunek nietrudno przekonać się o prawdziwości powyższego stwierdzenia.

drzwi1

Czyli wystarczy rozwiązać jednowymiarowy problem, w którym wejściem jest tablica \textrm{lcp}. Zanim jednak się tym zajmiemy, wróćmy na chwilę do samej redukcji. Czy przypadkiem nie okaże się ona zbyt kosztowna? Jeśli robilibyśmy ją dla każdego r_1 osobno, to pewnie tak. Łatwo jednak zauważyć, że po zmniejszeniu r_1 o jeden można zaktualizować posortowaną listę napisów c_i oraz tablicę \textrm{lcp} w czasie \mathcal{O}(m) (jednym liniowym sortowaniem; posortowana lista napisów to rzecz jasna tak naprawdę posortowana lista indeksów, a same napisy nie są jawnie konstruowane).
Od tego momentu zapominamy więc o oryginalnej dwuwymiarowej tablicy i koncentrujemy się na następującym problemie: znamy wszystkie \textrm{lcp}[j]=\textrm{lcp}(c_{j-1},c_j), gdzie c_0,c_1,\ldots,c_m to posortowane leksykograficznie napisy. Interesuje nas zsumowanie \textrm{lcp}(c_i,c_j) po wszystkich 0\leq i < j \leq m.

Z powyższej dyskusji wynika, że każde \textrm{lcp}(c_i,c_j) jest równe pewnemu \textrm{lcp}[k], gdzie k\in (i,j]. Można więc odwrócić sytuację i dla każdego \textrm{lcp}[k] policzyć pary i < j, dla których \textrm{lcp}[k] odpowiada \textrm{lcp}(c_i,c_j). Odpowiada należy tutaj rozumieć tak, że k jest najmniejszym indeksem wśród (i,j], dla którego \textrm{lcp}[k]=\min(c_{i+1},c_{i+1},\ldots,c_j). Nietrudno zauważyć, że tak naprawdę wymaga to wyznaczenia najmniejszego możliwego i oraz największego możliwego j, i te dwie kwestie są nie tylko zupełnie niezależne, ale też prawie (choć nie do końca) symetryczne. Pomyślmy więc o wyznaczaniu najmniejszego możliwego i. W tym celu wystarczy tylko znów przejrzeć wejście od lewej do prawej utrzymując stos! Widząc kolejne c_k zdejmujemy ze stosu wszystkie elementy, które są większe lub równe temu c_k. Następnie zauważamy, że i to prostu element znajdujący się na szczycie stosu po tej aktualizacji (jeśli stos jest pusty, przyjmujemy i=0). Pozwala to na wyznaczenie każdego i w zamortyzowanym czasie \mathcal{O}(1). Podobnie wyznaczamy wszystkie j i tym samym rozwiązujemy nasz jednowymiarowy problem w czasie \mathcal{O}(m). Co daje liniowe rozwiązanie oryginalnego zadania. Yay!

Advertisements

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s