کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430939 | 688234 | 2007 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A simple fast hybrid pattern-matching algorithm
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A simple fast hybrid pattern-matching algorithm A simple fast hybrid pattern-matching algorithm](/preview/png/430939.png)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 5, Issue 4, December 2007, Pages 682–695
Journal: Journal of Discrete Algorithms - Volume 5, Issue 4, December 2007, Pages 682–695
نویسندگان
Frantisek Franek, Christopher G. Jennings, W.F. Smyth,