A simple fast hybrid pattern-matching algorithm
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
Pearce, Adrian (1996)Spatial interpretation involves the intelligent processing of images for learning, planning and visualisation. This involves building systems which learn to recognise patterns from the content of unconstrained data such ...
Lee, Justin (2003)Mobile wireless sensor networks (MWSNs) will enable information systems to gather detailed information about the environment on an unprecedented scale. These selforganising, distributed networks of sensors, processors and ...
Smyth, Bill; Wang, Shu; Yu, Mao (2008)We describe a hybrid pattern-matching algorithm that works on both regular and indeterminate strings. This algorithm is inspired by the recently proposed hybrid algorithm FJS  and its indeterminate successor . ...