کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430884 688223 2013 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A computational framework for determining run-maximal strings
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A computational framework for determining run-maximal strings
چکیده انگلیسی

We investigate the function ρd(n)=max{r(x)|x is a (d,n)-string}ρd(n)=max{r(x)|x is a (d,n)-string}, where r(x)r(x) denotes the number of runs in a string x   and (d,n)(d,n)-string denotes a string of length n with exactly d   distinct symbols. The notion of an r-cover is presented and discussed with emphasis on the recursive computational determination of ρd(n)ρd(n). This notion is used as a key element of a computational framework for an efficient computation of the maximum number of runs. In particular, we were able to determine all previously known ρ2(n)ρ2(n) values for n⩽60n⩽60 in a matter of hours, confirming the results reported by Kolpakov and Kucherov, and were able to extend the computations up to and including n=74n=74. Noticeably, these computations reveal the unexpected existence of a binary run-maximal string of length 66 containing aaaaaaaa.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 20, May 2013, Pages 43–50
نویسندگان
, , ,