Zbornik radova Fakulteta tehničkih nauka u Novom Sadu

Elektrotehničko i računarsko inženjerstvo

God. 35 Br. 03 (2020): Zbornik radova fakulteta tehničkih nauka

IMPLEMENTACIJA I TESTIRANJE ALGORITAMA ZA TAČNO PODUDARANJE STRINGOVA

  • Branislav Trkulja
DOI:
https://doi.org/10.24867/07BE48Trkulja
Predato
March 4, 2020
Objavljeno
2020-03-04

Apstrakt

U radu su opisani algoritmi koji su najčešće u upotrebi za tačno podudaranje stringova. Razmatrani su “Brute force” metoda, algoritam Rabin-Karp, Knuth-Morris-Pratt i Boyer Moore algoritam. Na­brojani algoritmi su implementirani u C# programskom jeziku i izvršena su testiranja njihovih performasi. Rad sadrži rezultate dobijene testiranjem nad dve vrste testnih podataka. Jedna vrsta podataka su veštački generisani primeri koji treba da istaknu dobre i loše strane algo­ritama, dok drugu vrstu podataka čine realni primeri: tekst knjige „Rat i mir“ i CIM/XML fajl sa 2GB podataka.

Reference

[1] Herbert S. Wilf, “Algorithms and Complexity”, Summer 1994.
[2] C. Charras, T. Lecroq, „Handbook of Exact String-Matching Algorithms“, 2004.
[3] http://staff.ustc.edu.cn/~csli/graduate/algorithms/
book6/chap34.htm (pristupljeno u septembru 2019.)
[4] D. Gusfield, “Algorithms on Strings, Trees and Sequences. Computer science and computational biology”, 1997.
[5] https://www.geeksforgeeks.org/boyer-moore-algorithm-for-pattern-searching/ (pristupljeno u septembru 2019.)
[6] Ramshankar Choudhary, „Variation of Boyer-Moore String Matching Algorithm: A Comparative Analysis“, February 2012.
[7] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, „Introduction to algorithms“, 2001.