EMPIRICAL PERFORMANCE EVALUATION OF KNUTH MORRIS PRATT AND BOYER MOORE STRING MATCHING ALGORITHMS

Manyalgorithms have been proposed for string matching in order to find a specific pattern in a given text. These algorithms have been used in many applications such as software editors, genetics, Internet search engines, natural language processing, etc. Theaim of this paper is to evaluate the performance of two popularalgorithms:BoyerMoore (BM) and KnuthMorrisPratt (KMP) in terms of execution time. The algorithms have been programmed usingJava and Java Microbenchmark Harnessto evaluatetheirexecution timeusinganumber of experimentaltest scenarios.Resultsshowthat the BMalgorithm outperformed the KMPalgorithm in all test scenarios