7.11.2012
1. Kilka podstawowych definicji:
- Prefiks - początkowy fragment słowa.
- Sufiks - końcowy fragment słowa.
- Wzorzec - wyszukiwane słowo w tekście.
- Prefikso-sufiks - prefiks będący jednocześnie sufiksem słowa.
2. Algorytm KMP
- Wyznaczanie funkcji prefiksowej
- Zastosowanie do wyszukiwania wzorca w tekście w czasie liniowym.
3. Okresy i pierwiastki słowa
- Wyjaśnienie obu definicji.
- Związek między okresami słów, a prefikso-sufiksami.
- Lemat o okresowości.
4. Zadanie Okresy Słów z I etapu XIII Olimpiady Informatycznej.
5. Algorytm Manachera
- Wyjaśnienie co to jest palindrom.
- Przykładowa implementacja z objaśnieniem.
Ciekawy wykład o Algorytmach Tekstowych znajduje się TUTAJ
wersja strony: 3, ostatnia edycja: 16 Nov 2012 15:18