The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
复制标题
字符串中的游程数：线性上限的改进分析
DOI：
10.1007/11672142_14
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
W. Rytter
中科院分区：
文献类型：
--
作者：
W. Rytter
A run (or a maximal repetition) in a string is an inclusion-maximal periodic segment in a string. Let ρ(n) be the maximal number of runs in a string of length n. It has been shown in [8] that ρ(n)=O(n), the proof was very complicated and the constant coefficient in O(n) has not been given explicitly. We propose a new approach to the analysis of runs based on the properties of subperiods: the periods of periodic parts of the runs. We show that ρ(n) ≤ 5 n. Our proof is inspired by the results of [4], where the role of new periodicity lemmas has been emphasized.
