Not So Many Runs in Strings
Not So Many Runs in Strings
复制标题
字符串中没有那么多运行
DOI：
10.1007/978-3-540-88282-4_22
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Mathieu Giraud
中科院分区：
文献类型：
--
作者：
Mathieu Giraud
自从Kolpakov和Kucherov在[5，6]中的工作以来，人们知道ρ(N)，即字符串中的最大游程数，与字符串的长度N成线性关系。Franek和al给出了$3/(1+\Sqrt{5})n\sim 0.927n$的下界。[3，4]，而上界最近由Rytter，Puglisi等人以及Crohemore和Ilie(1.6n)[8.7.1]提供。然而，ρ(N)/n函数的已知性质很少。在这里，我们通过一个简单的论证证明，LIMn→∞ρ(N)/n是存在的，并且从未达到这个极限。此外，我们进一步研究了周期至多p的最大游程数ρp(N)的渐近行为，给出了一些微游程的一个新的界：我们证明了二进制串中至多有0.971个周期为9的游程。最后，该技术改进了先前最好的已知上界，表明长度为nis的二进制字符串的总游程数小于1.52n。
Since the work of Kolpakov and Kucherov in [5,6], it is known that ρ(n), the maximal number of runs in a string, is linear in the length nof the string. A lower bound of $3/(1 + \sqrt{5})n \sim 0.927n$ has been given by Franek and al. [3,4], and upper bounds have been recently provided by Rytter, Puglisi and al., and Crochemore and Ilie (1.6n) [8.7.1]. However, very few properties are known for the ρ(n)/nfunction. We show here by a simple argument that lim n→ ∞ ρ(n)/nexists and that this limit is never reached. Moreover, we further study the asymptotic behavior of ρ p (n), the maximal number of runs with period at most p. We provide a new bound for some microruns : we show that there is no more than 0.971 nruns of period at most 9 in binary strings. Finally, this technique improves the previous best known upper bound, showing that the total number of runs in a binary string of length nis below 1.52n.