Empirical Performance Evaluation of Knuth Morris Pratt and Boyer Moore String Matching Algorithms

Abstract

Many algorithms 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. The aim of this paper is to evaluate the performance of two popular algorithms: Boyer Moore (BM) and Knuth Morris Pratt (KMP) in terms of execution time. The algorithms have been programmed using Java and Java Microbenchmark Harness to evaluate their execution time using a number of experimental test scenarios. Results show that the BM algorithm outperformed the KMP algorithm in all test scenarios.

Publication
Journal of Duhok University 23-1