کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431640 | 688602 | 2012 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the maximal sum of exponents of runs in a string
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A run is an inclusion maximal occurrence in a string (as a subinterval) of a repetition v with a period p such that 2p⩽|v|2p⩽|v|. The exponent of a run is defined as |v|/p|v|/p and is greater than or equal to 2. We show new bounds on the maximal sum of exponents of runs in a string of length n. Our upper bound of 4.1n is better than the best previously known proven bound of 5.6n by Crochemore and Ilie (2008). The lower bound of 2.035n, obtained using a family of binary words, contradicts the conjecture of Kolpakov and Kucherov (1999), that the maximal sum of exponents of runs in a string of length n is smaller than 2n.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 14, July 2012, Pages 29–36
Journal: Journal of Discrete Algorithms - Volume 14, July 2012, Pages 29–36
نویسندگان
Maxime Crochemore, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń,