20.500.12556/DKUM-77237 Ukkonenov algoritem konstrukcije priponskega drevesa diplomsko delo Ukkonen's algorithm for suffix tree construction S pomočjo priponskih dreves lahko zelo preprosto in hitro izvajamo različne operacije nad nizi. Za gradnjo priponskih dreves obstajajo različni algoritmi. V diplomskem delu opi-šemo in implementiramo Ukkonenov algoritem, ki priponsko drevo zgradi v linearnem času. Najprej preučimo delovanje algoritma in tvorimo ustrezne podatkovne strukture. Sledi implementacija in preizkušanje. Z eksperimenti pokažemo karakteristike algoritma ob različnem številu znakov ter preverimo njegovo časovno in prostorsko zahtevnost. Different operations on strings can be executed efficiently using a suffix tree. Various algorithms exist for the suffix tree construction. Ukkonen’s algorithm is one of them andis considered in this thesis. The idea of the algorithm is presentedfirst. The used data structuresare described next,followed by implementation details. Our implementation of the Ukkonen’s algorithm is evaluated in regard to the spent CPU time and computer memory usage. The obtained implementation turns out stable and efficient. algoritmi podatkovne strukture analiza algoritmov časovna in prostorska zahtevnost algorithms data structures algorithm analysis space and time complexity true true false [Š. Horvat] Slovenski jezik Angleški jezik Diplomsko delo/naloga 2020-08-24 09:08:43 2020-11-03 11:10:11 2022-08-09 14:32:48 2020-11-19 03:22:37 2020 0 Maribor 0 Maribor V, 43 f. 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.422.63(043.2) 37249027 URN:SI:UM:DK:QHQ5OZNK UN_Horvat_Stefan_2020.pdf UN_Horvat_Stefan_2020.pdf 1 3A41B8680F8E6BBF0FC5FDE853AF72FC 668336e64e8d346b239d2ca74f86ecfc387dd238fe77cd949d829899c3523f7d c339a6c0-7c11-11eb-bb7a-00155d0001ca 20.500.12556/dkum/1d4274ec-e80a-4b2d-ab44-35319e8ff4bf https://dk.um.si/Dokument.php?lang=slv&id=144937 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0