MOKIP 11.01.2012
- Kilka definicji, czyli co to jest
- alfabet
- słowo
- prefiks, sufiks
- konkatenacja
- Wyszukiwanie wzorca w tekście - algorytm naiwny $O(nm)$
- Algorytm KMP (Knutha-Morrisa-Pratta)
- prefikso-sufiks: definicja, kilka ciekawych własności
- jak liczyć tablicę p (tablicę prefiksową)
- tutaj dobra implementacja (Jakuba Radoszewskiego)
- 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
- Zadanie Szablon z XII OI
- 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)
- A stąd zerżnąłem większość wykładu:)
wersja strony: 4, ostatnia edycja: 11 Jan 2012 21:30