Hledání vzorků v textu
Problém: Text 7"[1... n], vzorek P[l... m]. Existuje / tak, že T[i...i + m- 1] = P[l...m]?
► Jaké znáte způsoby řešení problému hledání vzorků v textu?
Hledání vzorků v textu
Uvažujme naivní algoritmus pro hledání vzorků v textu. Předpokládejme, že všechny znaky v P jsou různé. Jak dokážete naivní algoritmus zrychlit?
Hledání vzorků v textu - varianty
Předpokládejme, že vzorek P může kromě běžných symbolů i speciální symbol *, který reprezentuje libovolný počet libovolných znaků (i žádný). Jak můžete upravit známé algoritmy tak, aby hledaly výskyt takovýchto rozšířených vzorků?
K zamyšlení (na doma): Co kdyby vzorek kromě * obsahoval i speciální symbol ?, který reprezentuje jeden libovolný znak?
Hledání vzorků v textu - konečné automaty
► Sestrojte konečný automat pro vzorek aabab.
Hledání vzorků v textu - konečné automaty
► Sestrojte konečný automat pro vzorek aabab.
► Jak vypadá konečný automat pro vzorek se speciálním symbolem *?
Hledání vzorků v textu - konečné automaty
► Sestrojte konečný automat pro vzorek aabab.
► Jak vypadá konečný automat pro vzorek se speciálním symbolem *?
► Označme P k = P[l... k], tedy prvních k znaků vzorku P. Vzorek P je bez překryvů, pokud pro každé k, I platí, že je-li Pk sufixem P/f pak buď k = 0 nebo k — I. Jak vypadá konečný automat pro vzorek bez překryvů?
Hledání vzorků v textu - konečné automaty
► Sestrojte konečný automat pro vzorek aabab.
► Jak vypadá konečný automat pro vzorek se speciálním symbolem *?
► Označme P^ — P[l... k], tedy prvních k znaků vzorku P. Vzorek P je bez překryvů, pokud pro každé k, I platí, že je-li Pk sufixem P/f pak buď k = 0 nebo k = I. Jak vypadá konečný automat pro vzorek bez překryvů?
► Jak modifikovat algoritmus založený na konečných automatech tak, aby vypsal všechny výskyty vzorku v textu?
Hledání vzorků v textu - varianty
Co kdybychom měli více vzorků Pi, ..., P^l Dokážete upravit některý známý algoritmus tak, aby uměl v textu efektivně hledat libovolný z těchto vzorků?
Poznámka: Pro zjednodušení můžete předpokládat, že všechny vzorky mají stejnou délku.
Související příklady
Cyklická rotace
Cyklickou rotací textu 7"[1... r?] je text T [i... n] • 7"[1... / — 1] pro nějaké /. Mějme na vstupu dva řetězce A, B stejné délky. Chceme rozhodnout, zda je jeden z nich cyklickou rotací druhého.
► Jak můžeme tento problém vyřešit pomocí hledání vzorku v textu?
Související příklady
Nejdelší palindromický prefix
Máme zadaný text 7"[1... n] a chceme najít jeho co nejdelší prefix 7"[1.../], který je zároveň palindromem (čte se stejně zepředu i zezadu).
► Jak souvisí tento problém s hledáním vzorku v textu?
Související příklady
Hledání podstromů
Mějme dva binární stromy P, T. Chceme najít (všechny) podstromy stromu T, které mají stejnou strukturu jako strom P.
► Jak souvisí tento problém s hledáním vzorku v textu?