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