IMPLEMENTATION AND TESTING OF STRING MATCHING ALGORITHMS
DOI:
https://doi.org/10.24867/07BE48TrkuljaKeywords:
Text searching algorithms, Knuth-Morris-Pratt algorithm, Boyer Moore algorithm, Rabin Karp algorithmAbstract
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.
[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.
Downloads
Published
2020-03-04
Issue
Section
Electrotechnical and Computer Engineering
