Journal article
A simple fast hybrid pattern-matching algorithm
Combinatorial Pattern Matching, Vol.3537, pp.288-297
2005
Abstract
The Knuth-Morris-Pratt (KMP) pattern-matching algorithm guarantees both independence from alphabet size and worst-case execution time linear in the pattern length; on the other hand, the Boyer-Moore (BM) algorithm provides near-optimal average-case and best-case behaviour, as well as executing very fast in practice. We describe a simple algorithm that employs the main ideas of KMP and BM (with a little help from Sunday) in an effort to combine these desirable features. Experiments indicate that in practice the new algorithm is among the fastest exact pattern-matching algorithms discovered to date, perhaps dominant for alphabet size 8 or more.
Details
- Title
- A simple fast hybrid pattern-matching algorithm
- Authors/Creators
- F. Franěk (Author/Creator) - McMaster UniversityC.G. Jennings (Author/Creator) - Simon Fraser UniversityW.F. Smyth (Author/Creator) - McMaster University
- Publication Details
- Combinatorial Pattern Matching, Vol.3537, pp.288-297
- Publisher
- Springer Verlag
- Identifiers
- 991005545197707891
- Copyright
- 2005 Springer-Verlag Berlin Heidelberg
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
Metrics
72 Record Views