کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874758 | 1441206 | 2017 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Searching of gapped repeats and subrepetitions in a word
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Searching of gapped repeats and subrepetitions in a word Searching of gapped repeats and subrepetitions in a word](/preview/png/6874758.png)
چکیده انگلیسی
A gapped repeat is a factor of the form uvu where u and v are nonempty words. The period of the gapped repeat is defined as |u|+|v|. The gapped repeat is maximal if it cannot be extended to the left or to the right by at least one letter with preserving its period. The gapped repeat is called α-gapped if its period is not greater than α|u|. A δ-subrepetition is a factor whose exponent is less than 2 but is not less than 1+δ (the exponent of the factor is the quotient of the length and the minimal period of the factor). The δ-subrepetition is maximal if it cannot be extended to the left or to the right by at least one letter with preserving its minimal period. We reveal a close relation between maximal gapped repeats and maximal subrepetitions. Moreover, we show that in a word of length n the number of maximal α-gapped repeats is bounded by O(α2n) and the number of maximal δ-subrepetitions is bounded by O(n/δ2). Using the obtained upper bounds, we propose algorithms for finding all maximal α-gapped repeats and all maximal δ-subrepetitions in a word of length n (in assumption that the alphabet of the word is integer). The algorithm for finding all maximal α-gapped repeats has O(α2n) time complexity. For finding all maximal δ-subrepetitions we propose two algorithms. The first algorithm has O(nlogâ¡logâ¡nδ2) time complexity. The second algorithm has O(nlogâ¡n+nδ2logâ¡1δ) expected time complexity.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volumes 46â47, SeptemberâNovember 2017, Pages 1-15
Journal: Journal of Discrete Algorithms - Volumes 46â47, SeptemberâNovember 2017, Pages 1-15
نویسندگان
Roman Kolpakov, Mikhail Podolskiy, Mikhail Posypkin, Nickolay Khrapov,