کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430884 | 688223 | 2013 | 8 صفحه PDF | دانلود رایگان |

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.
Journal: Journal of Discrete Algorithms - Volume 20, May 2013, Pages 43–50