A Comparative Analysis of Various String Matching Algorithms

Abstract

String-matching is a very important subject in the wider domain of text processing. It is used in almost all the software applications starting from text editors to the complex Network Intrusion Detection Systems (NIDS) which uses signature matching based on string matching. There are different string matching algorithms for solving the string matching problem. Such algorithms can greatly reduce the response time of the software applications which uses the string matching. The research problem of this research is to analyse the efficiency of different string matching algorithms. The objective of this research is to evaluate the execution time of the string matching algorithms and compare the efficiency of the algorithms. This study focuses on four selected string matching algorithms which are Naïve algorithm, Brute-Force algorithm, Boyer-Moore algorithm and Knuth-MorrisPratt algorithm. The algorithms are tested against matching patterns with different lengths and the placement of the pattern (suffix, prefix or middle). The algorithms are written in Java Language and the execution time is measured in nanoseconds. The matching efficiencies of these algorithms are compared by the searching speed. It is observed that the performance of the Brute-Force algorithm and Naive algorithm is comparatively high. When considering the pattern placement, Brute-Force and Knuth-Morris-Pratt algorithms are faster when the pattern is in the prefix than suffix. Naive algorithm has no comparative difference of performance on the pattern placement