Improved string searching

1 March 1989

journal article
research article
Published by Wiley in Software: Practice and Experience

Vol. 19 (3) , 257-271
https://doi.org/10.1002/spe.4380190305

Abstract

We show that it is possible to improve the average time of the Boyer‐Moore string matching algorithm using more space. This is accomplished by applying a transformation that virtually increases the size of the alphabet in use. The improvement is such that for long patterns it is possible to obtain an algorithm more than 50 per cent faster than the original one. We include experimental results on random and English text. Some improvements for searching on English text are also discussed.

Keywords

This publication has 13 references indexed in Scilit:

The Boyer–Moore–Galil String Searching Strategies Revisited
SIAM Journal on Computing, 1986
Kantorovich-Type Inequalities
The American Mathematical Monthly, 1982
A comparison of three string matching algorithms
Software: Practice and Experience, 1982
A New Proof of the Linearity of the Boyer-Moore String Searching Algorithm
SIAM Journal on Computing, 1980
A Correct Preprocessing Algorithm for Boyer–Moore String-Searching
SIAM Journal on Computing, 1980
Practical fast searching in strings
Software: Practice and Experience, 1980
On improving the worst case running time of the Boyer-Moore string matching algorithm
Communications of the ACM, 1979
On the Worst-Case Behavior of String-Searching Algorithms
SIAM Journal on Computing, 1977
A fast string searching algorithm
Communications of the ACM, 1977
Fast Pattern Matching in Strings
SIAM Journal on Computing, 1977