prikaz prve stranice dokumenta Algoritmi za podudaranje znakovnih nizova
Access restricted to students and staff of home institution
master's thesis
Algoritmi za podudaranje znakovnih nizova
Zagreb: University of Zagreb, Faculty of Science, 2016. urn:nbn:hr:217:622889
Souček, Amalia
University of Zagreb
Faculty of Science
Department of Mathematics

Institutional repository: Repository of the Faculty of Science

Cite this document

Souček, A. (2016). Algoritmi za podudaranje znakovnih nizova (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:622889

Souček, Amalia. "Algoritmi za podudaranje znakovnih nizova." Master's thesis, University of Zagreb, Faculty of Science, 2016. https://urn.nsk.hr/urn:nbn:hr:217:622889

Souček, Amalia. "Algoritmi za podudaranje znakovnih nizova." Master's thesis, University of Zagreb, Faculty of Science, 2016. https://urn.nsk.hr/urn:nbn:hr:217:622889

Souček, A. (2016). 'Algoritmi za podudaranje znakovnih nizova', Master's thesis, University of Zagreb, Faculty of Science, accessed 23 December 2024, https://urn.nsk.hr/urn:nbn:hr:217:622889

Souček A. Algoritmi za podudaranje znakovnih nizova [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2016 [cited 2024 December 23] Available at: https://urn.nsk.hr/urn:nbn:hr:217:622889

A. Souček, "Algoritmi za podudaranje znakovnih nizova", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2016. Available at: https://urn.nsk.hr/urn:nbn:hr:217:622889

Metadata
TitleAlgoritmi za podudaranje znakovnih nizova
AuthorAmalia Souček
MentorGoranka Nogo (mentor)
Committee memberGoranka Nogo (predsjednik povjerenstva)
Committee memberMladen Vuković (član povjerenstva)
Committee memberFilip Najman (član povjerenstva)
Committee memberVjekoslav Kovač (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2016-04-27, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Abstract
U ovom radu opisali smo četiri važna algoritma koji rješavaju problem podudaranja znakovnih nizova: Knuth-Morris-Prattov, Boyer-Mooreov, Two ways i Shift or. Objasnili smo ideju svakog algoritma te računali njegovu složenost. Zaključili smo da Boyer-Mooreov algoritam ima sublinearnu složenost u prosječnom slučaju dok ostali imaju linearnu složenost u najgorem slučaju. Dobivene rezultate za zadnja tri opisana algoritma smo provjerili na testnim primjerima. Kao sto smo i očekivali, dobili smo da je Boyer-Mooreov brži od Two ways i Shift or. Takoder uočili smo kako je Shift or zapravo vrlo efikasan, usprkos jednostavnoj implementaciji, ali ograničen na dozvoljenoj dužini obrasca.
Abstract (english)
In this work we presented four important string matching algorithms: Knuth-Morris-Pratt, Boyer-Moore, Two ways and Shift or. We explained the idea behind each one and computed their time complexity. We concluded that the time complexity of Boyer-Moore is sublinear in the average case while the time complexity of the remaining algorithms is linear in the worst case. We tested our results for the last three algorithms on test data. As expected, Boyer-Moore was quicker than Two ways and Shift or. Besides, we noticed that Shift or is actually very efficient, even though its implementation is very simple. However, this algorithm is limited by the length of the pattern.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:217:622889
Study programmeTitle: Computer Science and Mathematics
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
Type of resourceText
File originBorn digital
Access conditionsAccess restricted to students and staff of home institution
Terms of useLicence In copyright icon
Created on2019-02-07 12:04:57