A simple fast hybrid pattern-matching algorithm
| dc.contributor.author | Smyth, William Fennell | |
| dc.contributor.author | Franek, F. | |
| dc.contributor.author | Jennings, C. | |
| dc.date.accessioned | 2017-01-30T11:02:01Z | |
| dc.date.available | 2017-01-30T11:02:01Z | |
| dc.date.created | 2014-10-08T06:00:33Z | |
| dc.date.issued | 2007 | |
| dc.identifier.citation | Smyth, 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.uri | http://hdl.handle.net/20.500.11937/7730 | |
| dc.identifier.doi | 10.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.publisher | Elsevier | |
| dc.title | A simple fast hybrid pattern-matching algorithm | |
| dc.type | Journal Article | |
| dcterms.source.volume | 5 | |
| dcterms.source.number | 4 | |
| dcterms.source.startPage | 682 | |
| dcterms.source.endPage | 695 | |
| dcterms.source.issn | 15708667 | |
| dcterms.source.title | Journal of Discrete Algorithms | |
| curtin.department | Digital Ecosystems and Business Intelligence Institute (DEBII) | |
| curtin.accessStatus | Open access via publisher |