Prednáška

Posledná prednáška predstavuje veľmi stručný úvod do problematiky algoritmov pre spracovanie reťazcov.

Základné informácie nájdete na slajdoch, s. 634-674, plný text v  Jeff Erickson: String Matching. Prehľad algoritmov s dobrým popisom a vizualizáciou je na www.

Prednáška prezentuje základné techniky, ktoré sa používajú v string matching algoritmoch: metódu Karpa a Rabina (aka fingerprinting alebo hašovanie), konečné automaty, algoritmus KMP a Boyer-Moore. Algoritmy sa líšia zložitosťou predspracovania a zložitosťou vyhľadávania (v najhoršom, najlepšom, očakávanom) prípade, viz slajd 637. String matching problém sa typicky rieši pre veľké vstupné inštancie a preto každé vylepšenie algoritmu s prejaví v čase výpočtu.  Jednotlivé algoritmy sa typicky líšia aj svojim chovaním na rôznych typoch vstupných inštancií, čo sa dá s výhodou využiť pri výbere toho "správneho" algoritmu. 

Cvičenie

Príklady na precvičenie. Kto hľadá, nájde.