Catalog Home Page

A simple fast hybrid pattern-matching algorithm

Franěk, F., Jennings, C.G. and Smyth, W.F. (2007) A simple fast hybrid pattern-matching algorithm. Journal of Discrete Algorithms, 5 (4). pp. 682-695.

Link to Published Version:
*Subscription may be required


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, apparently dominant for alphabet size above 15–20.

Item Type: Journal Article
Publisher: Elsevier
Copyright: © 2006 Elsevier B.V.
Item Control Page Item Control Page