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:)