On-line string matching algorithms: survey and experimental results
- 1 January 2001
- journal article
- research article
- Published by Taylor & Francis Ltd in International Journal of Computer Mathematics
- Vol. 76 (4), 411-434
- https://doi.org/10.1080/00207160108805036
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
This publication has 25 references indexed in Scilit:
- Experimenting with pattern-matching algorithmsInformation Sciences, 1996
- Speeding up two string-matching algorithmsAlgorithmica, 1994
- Fastest Pattern Matching in StringsJournal of Algorithms, 1994
- Fast text searchingCommunications of the ACM, 1992
- A variation on the Boyer-Moore algorithmTheoretical Computer Science, 1992
- Fast string searchingSoftware: Practice and Experience, 1991
- Experiments with a very fast substring search algorithmSoftware: Practice and Experience, 1991
- A very fast substring search algorithmCommunications of the ACM, 1990
- Algorithms for string searchingACM SIGIR Forum, 1989
- Implementation of the substring test by hashingCommunications of the ACM, 1971