Algoritem SA-IS za tvorbo priponskega polja

diplomsko delo

Daniel Kvar (Author), Borut Žalik (Mentor), Aljaž Jeromel (Co-mentor)

Abstract

Priponsko polje je podatkovna struktura, ki nam zelo učinkovito pomaga, kadar želimo izvajati določene operacije nad nizi, kot recimo: iskanje vzorca v nizu, iskanje najdaljšega ponavljajočega se niza in podobne. Obstaja več algoritmov za tvorbo priponskega polja. Algoritem SA-IS obljublja njegovo konstrukcijo v linearnem času, majhno prostorsko zahtevnost in hitrost v praksi. V diplomskem delu bomo najprej analizirali delovanje algoritma, sledila bo implementacija, testiranje in merjenje časa CPU ter porabo pomnilnika implementiranega algoritma.

Keywords

računalništvo;algoritem;podatkovna struktura;priponska polja;inducirano razvrščanje;časovna zahtevnost;diplomske naloge;

Data

Language:	Slovenian
Year of publishing:	2022
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
Publisher:	[D. Kvar]
UDC:	004.422.63(043.2)
COBISS:	128917507
Views:	531
Downloads:	141
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	SA-IS algorithm for suffix array construction
Secondary abstract:	A suffix array is a data structure that is very efficient for various string operations, such as finding a pattern in a string or finding the longest common prefix. Many algorithms exist for constructing suffix arrays. SA-IS algorithm promises its construction in linear time with good space efficiency and speed in practice. In this thesis, we explain the algorithm at first. Information about its implementation, testing, and measurements of spent CPU time and memory during the algorithm's execution follows.
Secondary keywords:	computer science;algorithm;data structure;suffix arrays;induced sorting;time complexity;
Type (COBISS):	Bachelor thesis/paper
Thesis comment:	Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informacijske tehnologije
Pages:	1 spletni vir (1 datoteka PDF (X, 27 f.))
ID:	16140482