Fórum studentů MFF UK

Selsky duKaz: Kdyz lezes na strom (i opakovane), spadnes nanejvys z te vysky kam jsi vylezl.

Ahaaa, tak takhle to je. Diky za tip.

V zapiskoch z Maresovej prednasky ( http://mj.ucw.cz/vyuka/0708/ads2/ads2.ps ) to myslim je.

Btw ten dokaz zlozitosti prace interpreteru spociva v tom, ze si uvedomis, ze na to, aby si k-krat zavolal funkciu fail musis najprv k-krat zavolat funkciu g, pretoze g ta v automate posuva o hladinu dalej od stavu 0, naopak fail ta posuva aspon o jednu hladinu blizsie k stavu 0. Inymi slovami celkovy pocet zavolani fail je mensi rovny celkovemu poctu zavolani g. No a g sa vola vola pre kazdy nacitany znak raz => celkovo sa vola m-krat ( kde m je velkost prehladavaneho textu ).

Snad som to nedoplietol :)

mohl by mi někdo poradit, kde najdu srozumnitelně (a nejlépe česky - anglicky sice rozumím dobře, ale učit se v aj mi moc nejde) vysvětlený důkaz složitosti algoritmu Aho-Corasick? protože Kučera nemá v textech k algovizi vůbec nic a Marešovy skripta tam je cosi o násobení polynomů, což nějak nechápu jak souvisí s AC...