Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

A simple fast hybrid pattern-matching algorithm

Franěk, F., Jennings, C.G. and Smyth, W.F. (2005) A simple fast hybrid pattern-matching algorithm. Lecture Notes in Computer Science, 3537 . pp. 288-297.

Link to Published Version: http://dx.doi.org/10.1007/11496656_25
*Subscription may be required

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.

Item Type: Journal Article
Publisher: Springer Verlag
Copyright: 2005 Springer-Verlag Berlin Heidelberg
URI: http://researchrepository.murdoch.edu.au/id/eprint/27892
Item Control Page Item Control Page