From 40796e11e32b8c528dcba23c5c2fc86713c1903e Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 29 Feb 2008 21:02:58 +0100 Subject: [PATCH] Opravena chyba v pseudokodu Ukkonenova algoritmu (podminka v bodech 10 a 15 byla prohozena). Diky Martinovi Kupcovi a Milanovi Strakovi za upozorneni. --- 10-suffix/10-suffix.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/10-suffix/10-suffix.tex b/10-suffix/10-suffix.tex index 9249c8a..abdcc72 100644 --- a/10-suffix/10-suffix.tex +++ b/10-suffix/10-suffix.tex @@ -296,13 +296,13 @@ bude hodit p \:::Pokud v~popisce této hrany po~$\tau$ následuje znak~$a$, pak je $\alpha a$ pøítomen. \:::Pokud nenásleduje, tak nebyl pøítomen, èili tuto hranu rozdìlíme: pøidáme na~ni nový vnitøní vrchol, do~nìj¾ povede hrana s~popiskou~$\tau$ a z~nìj zbytek pùvodní hrany a otevøená hrana do~nového listu. -\:Pokud $\alpha a$ byl pøítomen, tak $\alpha$ zkrátíme a test opakujeme: +\:Pokud $\alpha a$ nebyl pøítomen, tak $\alpha$ zkrátíme a test opakujeme: \::Je-li $\pi\ne\varepsilon$, nastavíme $\pi := \(\pi)$. V~opaèném pøípadì (jsme v~koøeni) zkrátíme $\tau$ o~znak zleva. \::Pár $(\pi,\tau)$ u¾ popisuje zkrácené slovo, ale nemusí být kanonický, tak¾e to je¹tì napravíme: \:::Dokud existuje hrana vedoucí z~$\pi$, její¾ popiska je prefixem slova $\tau$, tak se po~této hranì posuneme, èili prodlou¾íme $\pi$ o~tuto popisku a zkrátíme o~ni~$\tau$. \::Zpìt na~krok 2. -\:Pokud $\alpha a$ u¾ je pøítomen, zbývá pøidat $a$ k~$\alpha$ a zastavit se: +\:Pokud $\alpha a$ ji¾ byl pøítomen, zbývá pøidat $a$ k~$\alpha$ a zastavit se: \::$\tau := \tau a$. \::Kanonikalizace stejnì jako v~bodech 12--13.\foot{Dokonce jednodu¹¹í, proto¾e projdeme nejvý¹e jednu hranu.} \:Dopoèítáme zpìtné hrany (viz ní¾e). -- 2.39.2