On-line string matching algorithms: survey and experimental results

Abstract

In this paper we present a short survey and experimental results for well known sequential string matching algorithms. We consider algorithms based on different approaches including classical, suffix automata, bit-parallelism and hashing. We put special emphasis on algorithms recently presented such as Shift-Or and BNDM algorithms. We compare these algorithms in terms of the number of character comparisons and the running time for four different types of text: binary alphabet, alphabet of size 8, English alphabet and DNA alphabet.

Keywords:

• String Matching
• Pattern Matching
• String Searching
• Text Searching
• Text Editing

C.R. Categories:

• F.2.2
• L.5.2