10.01 - "Algorytmy tekstowe, skojarzenia"

1. Konstrukcja slownika slow bazowych w O(nlogn) z uzyciem sortowania pozycyjnego.
2. Zastosowania slownika slow bazowych:
   1. wyszukiwanie wzorca w tekscie (algorytm KMR),
   2. wyszukiwanie najdluzszego wspolnego podslowa k slow.
3. Wyszukiwanie wzorca w tekscie algorytmem KR (przez hasze).
4. Dwuwymiarowe uogolnienia algorytmow wyszukiwania wzorca w tekscie: KMP (tylko szkic), KMR i KR.
5. Zmiana tematu: algorytm znajdowania najliczniejszego skojarzenia w grafie dwudzielnym w zlozonosci O(VE) i o bardzo prostej i efektywnej implementacji (patrz skoj.cpp). Dowod poprawnosci algorytmu wykorzystujacy roznice symetryczna ("xorowanie") skojarzen: najliczniejszego i otrzymanego.
6. Szkic zagadnien maksymalnego przeplywu.

Literatura: do punktow 1-4: Banachowki, Diks, Rytter "Algorytmy i struktury danych", opis rozwiazania zadania Powtorzenia z finalu VII OI. Punkty 5 i 6: Cormen zagadnienie przeplywu strasznie rozwadnia, a skojarzenie sprowadza do przeplywu (smutnego w implementacji). Nie wiem, czy ww. zapis algorytmu skojarzenia jest gdzies dobrze opisany, mam nadzieje, ze kiedys bedzie dobrze opisany na MAIN-ie ;-)