Show simple item record

dc.contributor.authorSmyth, William Fennell
dc.contributor.authorFranek, F.
dc.contributor.authorJennings, C.
dc.date.accessioned2017-01-30T11:02:01Z
dc.date.available2017-01-30T11:02:01Z
dc.date.created2014-10-08T06:00:33Z
dc.date.issued2007
dc.identifier.citationSmyth, W.F. and Franek, F. and Jennings, C. 2007. A simple fast hybrid pattern-matching algorithm. Journal of Discrete Algorithms. 5 (4): pp. 682-695.
dc.identifier.urihttp://hdl.handle.net/20.500.11937/7730
dc.identifier.doi10.1016/j.jda.2006.11.004
dc.description.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, apparently dominant for alphabet size above 15–20.

dc.publisherElsevier
dc.titleA simple fast hybrid pattern-matching algorithm
dc.typeJournal Article
dcterms.source.volume5
dcterms.source.number4
dcterms.source.startPage682
dcterms.source.endPage695
dcterms.source.issn15708667
dcterms.source.titleJournal of Discrete Algorithms
curtin.departmentDigital Ecosystems and Business Intelligence Institute (DEBII)
curtin.accessStatusOpen access via publisher


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record