V petek, 26. aprila ob 14h bo doktorski študent Matevž Jekovec v prostorih LUSY na Jadranski 21 predstavil Ukkonenov algoritem za hitro gradnjo priponskih dreves [1]. Algoritem je poseben, ker v linearnem času zgradi priponsko drevo n pripon v skupni dolžini n^2/2 znakov. Čeprav zaradi slabe izrabe lokalnosti pomnilnika deluje počasneje od modernih algoritmov za gradnjo priponskih dreves (npr. ERa, predstavljena v [2]) novejši algoritmi še vedno potrebujejo O(n^2) primerjav znakov za gradnjo, vendar zaradi izboljšane lokalnosti za red velikosti pridobijo na dejanskem času.
[1] Ukkonen, E., 1995. On-Line Construction of Suffix Trees. Algorithmica, 14(3), pp.249–260.
[2] Mansour, E., Allam, A., Skiadopoulos, S. and Kalnis, P., 2011. ERA: efficient serial and parallel suffix tree construction for very long strings. Proceedings of the VLDB Endowment, 5(1), pp.49–60.