Experiments with 1-D string matching algorithms
Thomas Berry, John Moores University, Liverpool, UK

Abstract:
In this paper we present experimental results for string matching
algorithms which have a competitive theoretical worst case run time
complexity. Of these algorithms a few are already famous for their
speed in practice, such as the Boyer-Moore and its derivatives. We chose to
evaluate the algorithms by counting the number of comparisons made and by
timing how long they took to complete a given search. Using the experimental
results we were able to introduce a new string matching algorithm and
compared it with the existing algorithms by experimentation. These
experimental results clearly show that the new algorithm is more efficient
than the existing algorithms for our chosen data sets. Using the chosen data
sets over 1,500,000 separate tests were conducted to determine the most
efficient algorithm.