Improved string searching
Ricardo A. Baeza-Yates · Software Practice and Experience · 1989
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.
Cited by 69 works. doi:10.1002/spe.4380190305
Authors
References
- Fast Pattern Matching in Strings
- A fast string searching algorithm
- Practical fast searching in strings
- On improving the worst case running time of the Boyer-Moore string matching algorithm
- A New Proof of the Linearity of the Boyer-Moore String Searching Algorithm
- The Complexity of Pattern Matching for a Random String
- On the Worst-Case Behavior of String-Searching Algorithms
- The Boyer–Moore–Galil String Searching Strategies Revisited
- A Correct Preprocessing Algorithm for Boyer–Moore String-Searching
- A comparison of three string matching algorithms