hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
| Obě strany předchozí revize Předchozí verze Následující verze | Předchozí verze Následující verze Obě strany příští revize | ||
|
mgr-szz:in-pos:2-pos [2019/06/13 08:39] lachmanfrantisek |
mgr-szz:in-pos:2-pos [2019/06/13 09:29] lachmanfrantisek |
||
|---|---|---|---|
| Řádek 365: | Řádek 365: | ||
| ==== Algoritmy pro práci s řetězci ==== | ==== Algoritmy pro práci s řetězci ==== | ||
| - | <note tip>Podrobněji viz http://statnice.dqd.cz/home:inf:in17</note> | + | <note tip>Některé algoritmy (naivní, Karp-Rabin, automaty) jsou podrobněji rozepsány zde: http://statnice.dqd.cz/home:inf:in17</note> |
| Algoritmy pro: | Algoritmy pro: | ||
| Řádek 411: | Řádek 411: | ||
| <box 100% blue|KMP> | <box 100% blue|KMP> | ||
| - | * Nekonstruujeme celý automat ale před vyhledáváním vypočteme prefixovou funkci. | + | * Nekonstruujeme celý automat ale před vyhledáváním vypočteme **prefixovou funkci** pro vzorek. |
| - | * FIXME: podrobnosti | + | * Postupně pro každou pozici ve vzorku určíme délku největšího podvzorku, který je zároveň prefixem i sufixem dosud zpracované části vzorku. |
| + | * <math>\mathcal{O}(m)</math> | ||
| + | * Samotný výpočet pak probíhá obdobně jako naivní prohledávání, ale při neshodě (nebo nalezení vzorku) se: | ||
| + | * na textu nevracíme | ||
| + | * na vzorce posuneme na pole dle prefixové funkce | ||
| + | * <math>\mathcal{O}(n)</math> | ||
| </box> | </box> | ||
