Password suspects

Jednym z moich ulubionych zadań algorytmicznych jest Password Suspects z ACM World Finals 2008. Kapitan naszej drużyny przydzielił mi je wtedy mówiąc, że „to chyba jest dość proste”. Po dokładnym przeczytaniu treści tego oraz innych zadań, które miałem rozwiązać tamtego dnia uznałem, że to jednak nie jest zupełnie trywialne i póki co zajmę się innym, prostszym. Niestety, początek tego konkursu był dla nas nieudany i po około półtorej godziny zaczęliśmy być już mocno z tyłu. Jednocześnie stało się jasne, że jest to zadanie z kategorii tych, które trzeba zrobić by móc liczyć na dobry wynik i że jeśli uda nam się rozwiązać je szybko, będziemy mieli szansę nie stracić kontaktu z czołówką. Zapamiętałem to zadanie właśnie z powodu emocji, które towarzyszyły mi przy jego rozwiązywaniu. Poza tym okazało się ono dosyć oryginalne o tyle, że wymagało zastosowania dwóch różnych kategorii algorytmów. Tego typu zadania nie zdarzają się często i prawie zawsze stanowią ciekawe wyzwanie.

Zadanie

Oryginalną treść zadania można znaleźć tutaj, a jej skrócona wersja wyląda tak:

Dane jest wzorców oraz pewna liczba naturalna . Oblicz, ile jest słów, które jednocześnie

1. składają się z małych liter alfabetu angielskiego (a-z)
2. mają długość dokładnie
3. zawierają każdy z podanych wzorców jako spójne podsłowo.

Jeśli takich słów jest co najwyżej 42, należy dodatkowo je wszystkie wypisać.

Ograniczenia:

• 
• 
• Każdy z danych wzorców zawiera od do znaków i składa się wyłącznie z liter a-z.
• Odpowiedź nie przekroczy .

Przykładowo, dla , i danych wzorców „ab”, „ba” dopuszczalne są tylko 2 słowa: aba i bab.

Pierwszy pomysł

Krótka analiza zadania doprowadziła mnie do kilku wniosków. Po pierwsze, z całą pewnością nie jest to trywialne zadanie, które można rozwiązać w sposób zupełnie brutalny – wszystkich możliwych słów do sprawdzenia jest potencjalnie , czyli o wiele za dużo. Będzie trzeba więc skorzystać z jakiegoś sensownego algorytmu. Po drugie, dość intuicyjne wydało mi się przyjęcie, że największym problemem będzie tu samo policzenie ilości dopuszczalnych słów i póki co skupienie się jedynie na tym aspekcie zadania. Przypadek, gdy takich słów jest mało (co najwyżej 42) i trzeba je wszystkie wyznaczyć, wyglądał jedynie na dodatek, który miał umilić mi życie.

Wróciłem więc do analizy zadania, a dokładniej przemyślałem warunki narzucone na słowa, które trzeba zliczyć. Dwa pierwsze wyglądały na proste i naturalne, niestety jednak wszystko komplikował warunek trzeci, tj. zawieranie każdego z danych M wzorców jako spójnego podsłowa. Po sprawdzeniu kilku naiwnych podejść okazało się, że nie jest to proste. Chociażby dlatego, że niektóre spośród tych wzorców mogą mieć wspólne fragmenty, czy wręcz się w sobie zawierać. Ponadto, dopuszczalne są również słowa, w których jakiś z wzorców występuje kilka razy. Tak czy inaczej dość szybko zdałem sobie sprawę, że próby prostego zliczania szukanych słów nie mają szansy powodzenia. Na szczęście wtedy przyjrzałem się dokładniej ograniczeniom danych. Czasami naprawdę warto to zrobić!. , każdy z wzorców ma długość co najwyżej - ograniczenia są więc bardzo małe. Można w takim razie zaszaleć i spróbować jakiejś, nawet mocno skomplikowanej, strategii dynamicznej. Zaletą takiego podejścia jest to, że algorytmy dynamiczne są zazwyczaj dość proste. Zacząłem więc zastanawiać się nad tego typu rozwiązaniem.

Cóż, z praktyki wynika, że w tego typu zadaniach jednym z parametrów przy programowaniu dynamicznym jest długość zliczanych słów. Zazwyczaj okazuje się, że mając wyliczone „pewne informacje” dla wszystkich słów o długości i krótszych, można dość łatwo wyliczyć te same informacje dla słów długości . Powtarzając ten krok odpowiednią ilość razy otrzymamy w końcu wynik dla słów o długości zadanej w treści zadania. Trudność polega tutaj jednak na określeniu co to są te „pewne informacje”. Intuicyjnie, chciałbym znaleźć takie parametry dla programowania dynamicznego (poza długością słowa), które mając wyznaczone dla słów krótszych, będę umiał wyznaczyć dla słów dłuższych. No i chcę, żeby tych parametrów było jak najmniej, tak, aby móc zmieścić się w limitach pamięciowych i czasowych.

Jeden wzorzec

Mając w pamięci fakt, że muszę uporać się przede wszystkim z warunkiem trzecim (o wzorcach jako podsłowach) zabrałem się w końcu za ten problem. Pomocnicze pytanie, które można zadać sobie w takiej sytuacji to: „A jak można by to rozwiązać, gdyby był tylko jeden wzorzec?”. Dłuższa chwila zastanowienia i ten uproszczony przypadek okazuje się nie być aż tak trudny. Załóżmy, że wiem ile jest słów długości takich, że:

1. nie zawierają w sobie szukanego wzorca jako podsłowa i dokładnie p ostatnich liter słowa jest zgodne z p pierwszymi literami wzorca – wartość tą pamiętam w polu tablicy
2. zawierają w sobie szukany wzorzec jako podsłowo – wartość tą pamiętam w polu tablicy

Przypadek 1) jest prosty. Do każdego słowa zawierającego wzorzec mogę dopisać na końcu dowolną literę i dalej będzie ono zawierać ten wzorzec. Ponieważ jest tylko angielskich liter (czytelnik może to policzyć używając swoich palców u rąk, u nóg i palców u rąk koleżanki) to mamy znalezionych już słów zawierających wzorzec o długości .

Nieco trudniejszy jest przypadek 0). Załóżmy, że mamy słowo, które nie zawiera wzorca, ale jego ostatnich liter jest zgodne z pierwszymi literami tego wzorca, i że chcemy do tego słowa dopisać jakąś ustaloną literkę. Nazwę tę literę , ale oczywiście rozumowanie przebiega identycznie dla każdej wartości . Muszę wyliczyć, ile ostatnich liter słowa po dopisaniu będzie zgodnych z początkowym fragmentem wzorca. Doskonałym materiałem opisującym w jaki sposób to zrobić jest ta strona. Wyznaczoną liczbę nazwijmy . Dzięki niej mamy znalezionych słów o długości mających ostatnich liter zgodnych z pierwszymi literami wzorca. Dodatkowo, jeśli jest równe długości wzorca, oznacza to, że znaleźliśmy słów o długości zawierających cały wzorzec jako spójne podsłowo.

Całe rozumowanie ilustruje następujący (pseudo)kod:

1
2
3
4
5
6
7
8
9
10
11
12

int pref[dlugosc_wzorca] = oblicz_tablice_prefiksowa(wzorzec)
for(char next='a'; next<='z'; ++next)
  for(int p=0; p<dlugosc_wzorca; ++p) {
    int next_p = p;
    while(next_p>=0 && wzorzec[next_p + 1] != next)
      next_p = pref[ next_p ];
    if(next_p == dlugosc_wzorca)
      dp[k+1][1] += dp[k][0][p];
    else
      dp[k+1][0][next_p] += dp[k][0][p];
  }
dp[k+1][1] += 26 * dp[k][1];

W liniach (1)-(3) zeruję tablicę do której będę dodawał znalezione słowa długości o odpowiednich własnościach (początkowo nie znalazłem jeszcze żadnych takich słów). Linie (4)-(13) są odpowiedzialne za obsługę trudniejszego przypadku 0) – ich głębsze uzasadnienie czytelnik znajdzie na podanej przeze mnie stronie internetowej. Linia (14) odpowiada za prostszy przypadek 1). Rozwiązaniem całego problemu jest . Przypadek, gdy liczba ta jest mała i trzeba wypisać wszystkie znalezione słowa jest standardowym „dodatkiem” do algorytmu dynamicznego. Uporanie się z nim nie jest trudne i pozostawię to jako ćwiczenie Czytelnikowi.

Wracamy do oryginalnej wersji

Umiem więc już rozwiązać prostszą wersję zadania, taką, gdzie jest tylko jeden wzorzec. Spróbuję więc uogólnić to rozumowanie tak, by było ono w stanie obsłużyć nie jeden, lecz wzorców. Tak naprawdę trzeba sobie poradzić z uogólnieniem 2 rzeczy:

1. Zamiast pamiętać, czy wzorzec wystąpił w tekście, trzeba pamiętać, które wzorce już wystąpiły w tekście, a które jeszcze nie.
2. W uproszczonej wersji zadania dla jednego wzorca pamiętałem ile jego pierwszych liter jest zgodnych z ostatnimi literami słowa. Teraz trzeba w jakiś sposób pamiętać to dla każdego z wzorców.

Punkt a) okazuje się być dość prosty. To, które wzorce wystąpiły w tekście, można pamiętać w masce bitowej, tj. w liczbie składającej się z bitów. -ty bit tej liczby jest równy jeśli -ty wzorzec wystąpił już w tekście, 0 jeśli -ty wzorzec jeszcze nie wystąpił. Rozwiązania korzystające z masek bitowych są ogólnie dość kosztowne, gdyż do reprezentowania takiej maski potrzeba liczby -bitowej, czyli mogącej przyjąć aż różnych wartości. W tym zadaniu jednak , więc – dostatecznie mało, by rozwiązanie korzystające z takiego pomysłu okazało się sensowne (a przynajmniej nie wydawało się całkiem bezużyteczne).

Punkt b) jest trochę bardziej skomplikowany. Idealnym rozwiązaniem jest użycie w tym celu automatu Aho – Corasick. Automat ten jest w pewnym sensie uogólnieniem tablicy prefiksowej użytej w prostszym wariancie zadania, czyli właśnie tym, czego mi potrzeba. Mając zbudowaną tą strukturę dla podanych wzorców, można w algorytmie dynamicznym zamiast ilości ostatnich liter słowa zgodnych z wzorcem pamiętać numer stanu automatu. Wyznaczenie stanu po dodaniu litery jest jeszcze prostsze niż dla tablicy prefiksowej, gdyż wystarczy skorzystać z funkcji przejścia automatu. Ogólnie rozwiązanie korzystające z automatu Aho – Corasick jest w tym zadaniu bardzo eleganckie i zdecydowanie je polecam. Niestety jednak, szczegóły tej struktury wykraczają poza zakres artykułu. Chętni na pewno znajdą wystarczająco dużo materiałów na ten temat w internecie. Niemniej jednak można uporać się z punktem b) również w mniej elegancki sposób. Można na przykład pamiętać ilość liter zgodnych z ostatnimi literami słowa dla każdego wzorca z osobna. Wszystkich możliwości jest co prawda za dużo by pamiętać to w zupełnie brutalny sposób (nawet !), jednak łatwo przekonać się, że zdecydowana większość z nich nie może nigdy zajść. W praktyce, można pamiętać wszystkie sensowne możliwości np. korzystając ze struktury mapy, dostępnej w bibilotece stl w c++ i w java.utils w javie. Można również pamiętać dla którego wzorca zgodnych jest najwięcej liter oraz ilość liter zgodnych z tym wzorcem. Dla tych rozwiązań szczegóły implementacyjne są dość skomplikowane, więc nie będę się nad nimi rozwodził. Dla chętnych czytelników wgłębienie się w nie może jednak być dobrym ćwiczeniem.

Koniec?

Niestety, historia tego zadania nie ma szczęśliwego zakończenia. Pomimo usilnych starań nie udało się nam rozwiązać go w trakcie trwania zawodów. Nie zmienia to jednak faktu, że zadanie to szczególnie podoba mi się za to, że w interesujący sposób łączy w sobie programowanie dynamiczne z zaawansowanym algorytmem tekstowym. Uważam je również za okazję do ciekawej rozrywki i do nauczenia się czegoś nowego – i przede wszystkim tego życzę wszystkim Czytelnikom :)