Nieoficjalna strona przedmiotu

"Złożoność algorytmów na tekstach"

Na tej stronie znajduje się biblioteczka programów implementujących różne algorytmy tekstowe. Biblioteczka powstała na podstawie zajęć z przedmiotu "Złożoność algorytmów na tekstach", prowadzonego na Wydziale Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego przez prof. dr. hab. Wojciecha Ryttera.

Autorami programów w biblioteczce są Marek Cygan i Jakub Radoszewski. Programy składają się z gotowych do wykorzystania funkcji (w przypadku mniej obszernych i skomplikowanych algorytmów) lub z kodów źródłowych całych programów, wraz z kodem prezentującym ich działanie (w przypadku bardziej złożonych algorytmów).

Algorytmy wyszukiwania wzorca w tekście

• Algorytm Morrisa-Pratta wyszukiwania wzorca w tekście w czasie liniowym od sumy długości wzorca i tekstu - mp.cpp
• Algorytm Aho-Corasick, który jest symulacją algorytmu Morrisa-Pratta na wielu wzorcach jednocześnie w czasie proporcjonalnym do sumy długości tych wzorców i tekstu - aho-corasick.cpp

Algorytmy budowania struktur danych związanych ze słowami

Algorytmy te tworzą struktury danych o wielkości liniowej względem długości słowa. Zaprezentowane tu algorytmy mają złożoność czasową liniową.

• Wyliczanie tablic Bord i StBord, używanych odpowiednio w algorytmach Morrisa-Pratta i Knutha-Morrisa-Pratta - bord.cpp
• Wyliczanie tablicy PREF. Wartością PREF[i] jest długość najdłuższego prefiksu całego słowa, który występuje w słowie poczynając od i-tej litery - pref.cpp
• Budowanie drzewa sufiksowego algorytmem Ukkonena. Poza tym, program zawiera procedury konstruujące na podstawie drzewa sufiksowego tablice: SUF, SUF-odwrotną oraz LCP - sufiksowe.cpp
• Budowanie grafu podsłów (z ang. Directed Acyclic Word Graph - DAWG) algorytmem on-line. Kod nie jest jeszcze dokładnie przetestowany - dawg.cpp

Rozwiązania zadania Szablon z XII Olimpiady Informatycznej

Zadanie to, autorstwa prof. dr. hab. Wojciecha Ryttera, posiada dwa istotne rozwiązania: suboptymalne o złożoności O(n*log(n)), będące usprawnieniem brutalnej metody wykorzystującej algorytm MP oraz optymalne o złożoności O(n), pokazujące zupełnie inne podejście.

• Rozwiązanie liniowo-logarytmiczne, w Pascalu - szablon-nlogn.pas i w C++ - szablon-nlogn.cpp
• Rozwiązanie liniowe, w Pascalu - szablon-liniowy.pas i w C++ - szablon-liniowy.cpp

Inne ciekawe algorytmy

• Nowość!!! Minimalizacja automatu skończonego nad alfabetem unarnym, algorytm o o złożoności czasowej i pamięciowej O(n) - automat.cpp
• Badanie równoważności cyklicznej dwóch słów za pomocą pięknego algorytmu, zaprezentowanego np. w książce Banachowski, Diks, Rytter "Algorytmy i struktury danych" - cykliczna.cpp
• Obliczanie największych promieni palindromów parzystych oraz nieparzystych za pomocą algorytmu Manachera - również opisane w wyżej wymienionej książce - manacher.cpp
• Program wykonujący szybkie numerowanie sufiksów słów Fibonacciego w porządku leksykograficznym i sprawdzanie, czy otrzymany jest ten sam wynik w metodzie brutalnej (sortowanie sufiksów); jest to "doświadczalne" sprawdzenie spostrzeżenia prof. dr. hab. Wojciecha Ryttera - fibsuf.cpp

Jest także możliwość pobrania całej paczki ze wszystkimi kodami: teksty.tgz.