Electrotechnical and Computer Engineering
Vol. 35 No. 03 (2020): Proceedings of the Faculty of Technical Sciences
IMPLEMENTATION AND TESTING OF STRING MATCHING ALGORITHMS
Abstract
This paper describes the most commonly used algorithms for exact string matching. The Brute force method, the Rabin-Karp algorithm, the Knuth-Morris-Pratt algorithm and the Boyer Moore algorithm are discussed. The above algorithms were implemented in C # programming language and their performance was tested. The paper contains the results obtained by testing over two types of test data. One type of data is artificially generated examples that should highlight the good and bad sides of algorithms, while the other type of data is real examples: a 3226571 character text book and CIM / XML file with 2GB data.
References
[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.