MOKIP 11.01.2012

1. Kilka definicji, czyli co to jest
   • alfabet
   • słowo
   • prefiks, sufiks
   • konkatenacja
2. Wyszukiwanie wzorca w tekście - algorytm naiwny $O(nm)$
3. Algorytm KMP (Knutha-Morrisa-Pratta)
   • prefikso-sufiks: definicja, kilka ciekawych własności
   • jak liczyć tablicę p (tablicę prefiksową)
   • tutaj dobra implementacja (Jakuba Radoszewskiego)
4. Do czego jeszcze przydaje się tablica prefiksowa
   • znajdowanie najkrótszego okresu (jest to prefiks słowa o długości $n - p[n]$)
   • znajdowanie pierwiastka pierwotnego
5. Zadanie Szablon z XII OI
6. Zadanie domowe:
   • Antysymetria z XVII OI - ale najpierw trzeba poczytać o algorytmie Manachera (potem już jest łatwo). Jeśli algorytm Manachera wydaje się niezrozumiały, nie należy się martwić. Ten algorytm jest dziwny, jeżeli kiedyś będzie czas, to zostanie omówiony na kółku.
   • Palindromy z XIII OI (trudne, przyda się wiedza o pierwiastkach słów)

1. A stąd zerżnąłem większość wykładu:)