کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431733 | 688618 | 2007 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Parameterized matching with mismatches
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The problem of approximate parameterized string searching consists of finding, for a given text t=t1t2…tnt=t1t2…tn and pattern p=p1p2…pmp=p1p2…pm over respective alphabets ΣtΣt and ΣpΣp, the injection πiπi from ΣpΣp to ΣtΣt maximizing the number of matches between πi(p)πi(p) and titi+1…ti+m−1titi+1…ti+m−1(i=1,2,…,n−m+1)(i=1,2,…,n−m+1). We examine the special case where both strings are run-length encoded, and further restrict to the case where one of the alphabets is binary. For this case, we give a construction working in time O(n+(rp×rt)α(rt)log(rt))O(n+(rp×rt)α(rt)log(rt)), where rprp and rtrt denote the number of runs in the corresponding encodings for y and x, respectively, and α is the inverse of the Ackermann's function.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 5, Issue 1, March 2007, Pages 135–140
Journal: Journal of Discrete Algorithms - Volume 5, Issue 1, March 2007, Pages 135–140
نویسندگان
Alberto Apostolico, Péter L. Erdős, Moshe Lewenstein,