A simple fast hybrid pattern-matching algorithm
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...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
Elsevier
2007
|
| Online Access: | http://hdl.handle.net/20.500.11937/7730 |
| _version_ | 1848745453938540544 |
|---|---|
| author | Smyth, William Fennell Franek, F. Jennings, C. |
| author_facet | Smyth, William Fennell Franek, F. Jennings, C. |
| author_sort | Smyth, William Fennell |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T06:17:36Z |
| format | Journal Article |
| id | curtin-20.500.11937-7730 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T06:17:36Z |
| publishDate | 2007 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-77302017-09-13T14:35:06Z A simple fast hybrid pattern-matching algorithm Smyth, William Fennell Franek, F. Jennings, C. 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. 2007 Journal Article http://hdl.handle.net/20.500.11937/7730 10.1016/j.jda.2006.11.004 Elsevier unknown |
| spellingShingle | Smyth, William Fennell Franek, F. Jennings, C. A simple fast hybrid pattern-matching algorithm |
| title | A simple fast hybrid pattern-matching algorithm |
| title_full | A simple fast hybrid pattern-matching algorithm |
| title_fullStr | A simple fast hybrid pattern-matching algorithm |
| title_full_unstemmed | A simple fast hybrid pattern-matching algorithm |
| title_short | A simple fast hybrid pattern-matching algorithm |
| title_sort | simple fast hybrid pattern-matching algorithm |
| url | http://hdl.handle.net/20.500.11937/7730 |