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

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
نویسندگان
, , , , ,