Algoritmi za podudaranje znakovnih nizova

Souček, Amalia (2016) Algoritmi za podudaranje znakovnih nizova. Diploma thesis, Faculty of Science > Department of Mathematics.

[img]
Preview
PDF
Language: Croatian

Download (265kB) | Preview

Abstract

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.

Item Type: Thesis (Diploma thesis)
Supervisor: Nogo, Goranka
Date: 2016
Number of Pages: 35
Subjects: NATURAL SCIENCES > Mathematics
Divisions: Faculty of Science > Department of Mathematics
Depositing User: Iva Prah
Date Deposited: 19 May 2016 13:59
Last Modified: 19 May 2016 13:59
URI: http://digre.pmf.unizg.hr/id/eprint/4844

Actions (login required)

View Item View Item