Algoritmi za podudaranje znakovnih nizova

master's thesis

• Author: Amalia Souček
• Mentor: Goranka Nogo (mentor)
• Committee member: Goranka Nogo (predsjednik povjerenstva)
• Committee member: Mladen Vuković (član povjerenstva)
• Committee member: Filip Najman (član povjerenstva)
• Committee member: Vjekoslav Kovač (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2016-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: Knuth-Morris-Prattov algoritam; Boyer-Mooreov algoriam; Two ways algoritam; Shift or algoriatm; složenost algoritma
• Keywords (english): Knuth-Morris-Pratt algorithm; Boyer-Moore algorithm; Two ways algorithm; Shift or algorithm; algorithm complexity
• Language: croatian
• URN:NBN: urn:nbn:hr:217:622889
• Study programme: Title: 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 resource: Text
• File origin: Born digital
• Access conditions: Access restricted to students and staff of home institution
• Created on: 2019-02-07 12:04:57