Brzydkie słowa

Dzisiaj zmierzymy się z zadaniem o zliczaniu nieskończonych słów. A nawet lepiej: dwustronnie nieskończonych! Oczywiście nie przeszkodzi nam to w uzyskaniu złożoności liniowej. No, zliczanie wszystkich takich słów pewnie nie ma zbyt wiele sensu, więc naszym celem jest policzenie tylko tych, które nie zawierają żadnego z podanych zabronionych podsłów.

Jest to kolejne świetne zadanie z serii Andrew Stankevich Contest. Oryginalnie pojawiło się jako problem C na zawodach numer 17, treść można zobaczyć tutaj. Z tej oryginalnej treści właściwie interesuje nas tylko definicja dwustronnie nieskończonego słowa, ale równie dobrze można ją sobie wymyślić samemu wiedząc, że takim słowem jest na przykład \ldots aaaabbbb\ldots. Na wejściu dostajemy rozmiar alfabetu (myślmy, że jest to \{a,b\}) i listę zabronionych słów. Nie ma ich za dużo (bo co najwyżej 1000) i nie są one szczególnie długie (bo długości co najwyżej 10), lecz nie będziemy specjalnie korzystać ani z jednego, ani z drugiego. Jeśli jest nieskończenie wiele różnych dwustronnie nieskończonych słów, który nie zawierają żadnego z tych zabronionych podsłów, należy wypisać -1. W przeciwnym wypadku jesteśmy proszeni o podanie tej skończonej liczby.

Podstawową trudnością w tym zadaniu jest pewnie to, że ciężko wyobrazić sobie takie dwustronnie nieskończone słowa. Spróbujmy więc może najpierw rozwiązać prostszą wersję, w której interesują nas jednostronnie nieskończone słowa.

Powiedzmy, że mamy takie słowo a_1 a_2 a_3\ldots, gdzie a_i oznacza i-tą literę. Jak sprawdzić, że nie występuje w nim żadne z podanych na wejściu słów w_i? Pewnie korzystając z tej samej metody, której używa się do wyszukiwania zbioru podanych słów w skończonym słowie, czyli automatu Aho-Corasick (Corasick, a nie Corasicka, otóż bowiem Corasick była kobietą!). Jest to dość naturalne uogólnienie automatu, którego używa się zwykle do wyszukiwania jednego wzorca. Przypomnijmy, że taki automat ma jeden stan dla każdego możliwego prefiksu wzorca. Stan odpowiadający całemu wzorcowi jest akceptujący, a przejścia są dobrane tak, aby po przeczytaniu słowa a_1 a_2 \ldots a_i stan odpowiada najdłuższemu sufiksowi a_1 a_2 \ldots a_i, który jest prefiksem wzorca. W sytuacji, gdy mamy kilka wzorców, tworzymy jeden stan dla każdego słowa, które jest prefiksem jednego z nich (może być tak, że jedno słowo jest prefiksem kilku wzorców; tak czy inaczej, jednemu słowu odpowiada dokładnie jeden stan). Akceptujące są dokładnie te stany, które odpowiadają całym wzorcom (zakładamy tutaj, że żaden wzorzec nie wystąpuje w innych; w szczególności, są one wszystkie parami różne), a przejścia są dobrane tak, aby po przeczytaniu słowa a_1 a_2 \ldots a_i stan odpowiada najdłuższemu sufiksowi a_1 a_2 \ldots a_i, który jest prefiksem jakiegoś wzorca. Skonstruowanie funkcji przejścia dla podanego zbioru wzorców nie jest trudne, jeśli nie musimy się martwić o złożoność (a w zasadzie tak będzie w tym zadaniu), ale przy odrobinie uwagi jest to możliwe w czasie liniowym od sumy długości wzorców (jeśli zakładamy, że alfabet ma stały rozmiar, nie jest to szczególnie trudne, lecz bez takiego założenia wymaga pewnej ostrożności). Opis konstrukcji pewnie dość łatwo znaleźć choćby na wikipedii, więc nie będziemy się nad tym specjalnie rozwodzić. Zamiast tego popatrzymy na prosty przykład, w którym mamy trzy słowa w_1=\texttt{aaa}, w_2=\texttt{ba} i w_3=\texttt{abb}.

brzydkie

Aby sprawdzić, czy w danym słowie wysŧepuje jeden ze wzorców, wystarczy przejść odpowiadającą mu ścieżką. Jeśli znajdzie się na niej choć jeden stan akceptujący, znaleźliśmy jakiś wzorzec. Czyli skonstruowanie poprawnego słowa, w którym nie występuje żaden ze wzorców, sprowadza się do skonstruowania ścieżki, która starannie unika stanów akceptujących. Aby uprościć sobie życie, usuńmy z automatu wszystkie stany akceptujące. Wtedy zliczanie jednostronnie nieskończonych słów sprowadza się do zliczania różnych nieskończonych ścieżek, które zaczynają się w ustalonym wierzchołku startowym odpowiadającemu słowu pustemu.

Daje nam to dość wygodny sposób myślenia o całej sytuacji. Przypomnijmy, że naszym celem jest stwierdzenie, że takich ścieżek jest nieskończenie wiele, lub ich policzenie. To może zastanówmy się najpierw, kiedy jest ich skończenie wiele?

Cały automat jest niewątpliwie skończony (no, gdyby nie był, stwierdzenie, że potrafimy go skonstruować w czasie liniowym, było by nawet nie ryzykowne, a wręcz bez sensu). Nieskończona ścieżka musi więc prędzej lub później ponownie odwiedzić jakiś wierzchołek. To zaś oznacza, że w automacie jest przynajmniej jedna nietrywialna silnie spójna składowa (nietrywialna oznacza tu, że jest w niej przynajmniej jedna krawędź, choć być może jest tylko jeden wierzchołek). Popatrzmy na taką nietrywialną silnie spójną składową.

Lemat. Jeśli w automacie istnieje nietrywialna silnie spójna składowa, która jest osiągalna z wierzchołka startowego, ale nie jest cyklem prostym, czyli postaci v_1\rightarrow v_2\rightarrow\ldots\rightarrow v_\ell\rightarrow v_1, to w automacie mamy nieskończenie wiele różnych nieskończonych ścieżek.

Dowód. Jeśli silnie spójna składowa jest nietrywialna, lecz nie jest postaci v_1\rightarrow v_2\rightarrow\ldots\rightarrow v_\ell\rightarrow v_1, można znaleźć w niej dwa cykle (niekoniecznie proste, choć jeden z nich pewnie mógłby być prosty) startujące w tym samym wierzchołek v, których etykiety tworzą słowa x i y o takiej własności, że jedno nie jest prefiksem drugiego. Ani drugie nie jest prefiksem pierwszego. Skoro składowa jest osiągalna ze stanu poczatkowego, to istnieje słowo z takie, że mamy ścieżkę ze stanu początkowego do v, której etykieta to dokładnie z. A to oznacza, że dowolne słowo postaci z\{x,y\}^\infty jest etykieta nieskończonej ścieżki! Co więcej, warunek nałożony na x i y gwarantuje, że wszystkie te słowa są różne, czyli jest ich bardzo dużo.

Należy pewnie usunąć z automatu stany, które nie są osiągalne ze stanu początkowego, a następnie podzielić pozostałe na silnie spójne składowe. Jeśli choć jedna z nich jest nietrywialna, lecz nie jest cyklem prostym, możemy zakończyć pracę. W przeciwnym wypadku automat, z którym pracujemy, ma prosta strukturę. No, może nie prostą, ale prostszą niż pięc minut temu.

Wiemy więc, że wszystkie nietrywialne silnie spójne składowe mają wyjątkowo prosta strukturę. Ale może dałoby się powiedzieć nawet więcej? Wybierzmy sobie dwie takie silnie spójne składowe (rzecz jasna, osiągalne z wierzchołka startowego). Czy może być tak, że da się dojść z jednej do drugiej?

Lemat. Jeśli w automacie istnieją dwie różne nietrywialne silnie spójne składowe, z których pierwsza jest osiągalna z wierzchołka startowego, a druga z pierwszej, to w automacie mamy nieskończenie wiele różnych nieskończonych ścieżek.

Dowód. Jeśli mamy takie dwie różne nietrywialne silne spójne składowe, to można wskazać dwa różne wierzchołki u i v takie, że u jest osiągalny z wierzchołka startowego ścieżką, której etykieta to x, v jest osiągalny z u ścieżką, której etykieta to y, a ponadto u i v leżą na cyklach, których etykiety tworzą słowa (odpowiednio) x' i y'. Oznacza to, że dowolne słowo postaci x (x')^i y (y')^\infty jest etykietą jakiejś nieskończonej ścieżki. Co nawet lepsze, wszystkie takie słowa są różne.

Czyli sytuacja wygląda następująco: po usunięciu stanów, które nie są osiągalne ze stanu początkowego, i podzieleniu pozostałej części na silnie spójne składowe, należy sprawdzić, czy każda z nietrywialnych silnie spójnych składowych jest cyklem prostym, oraz czy jest tak, że z żadnej nietrywialnej silnie spójnie składowej nie da się dotrzeć do innej silnie spójnej składowej. Obydwa warunki można łatwo sprawdzić w czasie liniowym od rozmiaru grafu. Co dalej? Przypomnijmy sobie, że celem jest zliczenie różnych nieskończonych ścieżek. Jeśli każda nietrywialna silnie spójna składowa jest cyklem prostym, i nie da się z niej „uciec” do innej nietrywialnej silnie spójnej składowej, to każda taka nieskończona ścieżka prędzej lub później „utyka” w jakiejś silnie spójnej składowej, no i po prostu kręci się po niej w kółko. Czyli tak naprawdę wystarczy zliczyć różne (skończone) ścieżki, które zaczynają się w wierzchołku startowym, kończą w jakimś wierzchołku należącym do nietrywialnej silnie spójnej składowej, a poza tym przechodzą tylko przez wierzchołki należące do trywialnych silnie spójnych składowych. Więc tak naprawdę zredukowaliśmy problem do zliczania różnych ścieżek w DAGu! Co, rzecz jasna, wymaga tylko czasu liniowego (OK, jest tutaj jeden szczegół: w ogólnym przypadku takich ścieżek może być naprawdę dużo, i być może potrzebowalibyśmy do tego zliczania własnej arytmetyki; na szczęście nie jest tak w tym konkretnym przypadku, ale darujmy sobie drążenie tej lekko kłopotliwej kwestii).

Tyle jeśli chodzi o zliczanie poprawnych jednostronnie nieskończonych słów. Zabierzmy się więc za zliczanie takich, które są dwustronnie nieskończone!

Dość niewygodne staje się teraz to, że takie dwustronnie nieskończone słowa pewnie odpowiadają dwustronnie nieskończonym ścieżkom, które jakby nie mają początku. Nie ma więc sensu mówienie o wierzchołku początkowym. Co nawet bardziej niewygodne, mówienie o różnych takich słowach wymaga pewnej ostrożności, gdyż równość dwóch dwustronnie nieskończonych słów x i y oznacza, że istnieje przesunięcie i\in\mathbb{Z}, dla którego x_i = y_{i+j} dla każdego j\in\mathbb{Z}. Łatwo się więc nabrać, że dwa takie słowa są różne mimo, że tak naprawdę jedno jest przesunięciem drugiego. Mimo to, warto jeszcze raz popatrzeć na silnie spójne składowe. Okazuje się, że znów mają one dość prostą strukturę.

Lemat. Jeśli w automacie istnieje nietrywialna silnie spójna składowa, która nie jest cyklem prostym, czyli postaci v_1\rightarrow v_2\rightarrow\ldots\rightarrow v_\ell\rightarrow v_1, to możemy skonstruować nieskończenie wiele poprawnych dwustronnie nieskończonych słów.

Dowód. Podobnie jak w pierwszym dowodzie, zakładamy istnienie silnie spójnej składowej, która nie jest takiej postaci, i znajdujemy w niej dwa różne cykle startujące w tym samym wierzchołku v, których etykiety tworzą słowa x i y. Zakładamy, że pierwszy cykl jest prosty, oraz że żadne ze słów nie jest prefiksem drugiego. Chcielibyśmy skonstruować nieskończenie wiele dwustronnie nieskończonych słów sklejając ze sobą x i y, czyli tworząc słowa, które przypominają \ldots xxyyyxyxyyxyxx \ldots. Musimy jednak uważać, aby utworzone słowa były parami różne. Okazuje się to prostsze, jeśli konstruowane słowa są postaci \ldots xxxxxxxxy\{x,y\}^\infty, czyli najpierw mamy tam nieskończenie wiele kopii x, potem jedno y, a potem dowolną kombinację x i y. Spróbujmy przekonać się, że dla dwóch różnych kombinacji otrzymujemy różne dwustronnie nieskończone słowa. Jest tak dlatego, że równość dwóch słów takiej postaci oznacza, że cały (nieskończony) prefiks postaci \ldots xxxxxxy w jednym słowie musi przejść na taki sam prefiks w drugim. Zobaczenie, że tak jest, wymaga chwili zastanowienia nad tym, co właściwie „kodują” poszczególne stany w naszym automacie.

Czyli wiemy już, że wszystkie nietrywialne silnie spójne składowe muszą mieć prostą strukturę. Czy może być tak, że z jednej takiej składowej da się dojść do drugiej? Pewnie tak, wystarczy wyobrazić sobie, że takie przejście odpowiada ścieżce postaci \ldots aaaabbbb\ldots. Czy sytuacja może być jednak bardziej skomplikowana, czyli czy możemy mieć trzy nietrywialne silnie spójne składowe o takiej własności, że z pierwszej można przejść do drugiej, a z drugiej do trzeciej?

Taka sytuacja nie jest możliwa. Oznaczałaby by bowiem, że można skonstruować nieskończenie wiele różnych dwustronnie nieskończonych słów postaci \ldots xxxxx'y^i y' z^\infty. Czyli jeśli popatrzymy się na DAG silnie spójnych składowych utworzony dla pozostałej części automatu, wszystkie nietrywialne silnie spójne składowe są w nim źródłami lub ujściami (mogę też być wierzchołkami izolowanymi, czyli źródłem i ujściem jednocześnie). Przypomnijmy, że interesują nas dwustronnie nieskończone słowa. Każde takie słowo albo cały czas kręci się po tej samej nietrywialnej silnie spójnej składowej, albo najpierw kręci się (nieskończenie wiele razy) po jednej, a potem (również nieskończenie wiele razy) po drugiej, przy czym w międzyczasie musi jakoś między nimi przejść. Czyli takie słowo tak naprawdę odpowiada ścieżce w DAGu silnie spójnych składowych, która zaczyna i kończy się w wierzchołku odpowiadającym silnie spójnej składowej!

No dobra, takie ścieżki pewnie łatwo zliczyć. W końcu jest to nic innego niż zliczanie różnych ścieżek w DAGu. Ale czy rzeczywiście dwie różne ścieżki odpowiadają różnym dwustronnie nieskończonym słowom? W tym momencie przydatna jest poniższa obserwacja.

Obserwacja. Etykiety cykli prostych odpowiadających różnym nietrywialnym silnie spójnym składowym są parami różne. Co więcej, każda z takich etykiet jest słowem prymitywnym, czyli takim, którego nie da się przedstawić jako potęgę krótszego słowa, oraz żadna z etykiet nie jest cyklicznym przesunięciem innej.

Dlaczego tak jest? Znów trzeba wyobrazić sobie, co właściwie kodują poszczególne stany naszego automatu. Nie wiem jak to zgrabnie opisać, pozostawiam więc wyobraźni Czytelnika 🙂

Mając obserwację jest już łatwo. Mówi ona tak naprawdę tyle, że zaczynając (lub kończąc) ścieżkę w różnych nietrywialnych silnie spójnych składowych otrzymujemy różne słowa. Czyli wystarczy tylko policzyć różne ścieżki w DAGu, co nie jest szczególnie trudne. A konkretniej, może być wykonane używając liniowo wielu operacji. No, znów pojawia się tutaj kwestia, którą zignorowaliśmy już wcześniej: zakładamy tutaj, że dodanie do siebie dwóch liczb to jedna operacja, a być może te liczby mogą być całkiem spore. Okazuje się jednak, że w tym konkretnym przypadku nie może tak być. Niestety nie mam pomysłu na ładny argument dlaczego, pozostawiam to więc dociekliwemu Czytelnikowi.

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