کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
439023 | 690413 | 2010 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Optimality of some algorithms to detect quasiperiodicities
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Improving a 1993 algorithm of Apostolico and Ehrenfeucht, independently Iliopoulos and Mouchard in 1999 and Brodal and Pedersen in 2000 provided O(nlog(n)) algorithms to determine all maximal quasiperiodicities of a word of length n. We show here the optimality of this bound providing an infinite family of words w containing O(|w|log|w|) maximal quasiperiodicities. We also show that this bound is not reached for the celebrated family of Fibonacci words.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 411, Issues 34–36, 17 July 2010, Pages 3110-3122
Journal: Theoretical Computer Science - Volume 411, Issues 34–36, 17 July 2010, Pages 3110-3122