The number of runs in a string
The number of runs in a string
复制标题
字符串中的运行次数
DOI：
10.1016/j.ic.2007.01.007
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
W. Rytter
中科院分区：
文献类型：
--
作者：
W. Rytter
字符串中的游程是字符串中不可扩展(具有相同最小周期)的周期段。游程集合对应于字符串中的内部周期的结构。字符串的周期性得到了广泛的研究，在理论和实践(词的组合学、模式匹配、计算生物学)中都具有重要的意义。设ρ(N)是长度为n的串的最大游程数，证明了ρ(N)=O(N)，证明非常复杂，并且没有明确给出O(N)中的常系数。我们揭开了ρ(N)的线性上界的证明，并基于游程的子周期的性质提出了一种新的游程分析方法：游程的周期部分。我们证明了ρ(N)≤3.44n，并且最多存在周期大于87的0.67n游程。这支持了所有游程的个数小于n的猜想。我们还给出了一个全新的线性界的证明，并发现了几个新的有趣的“周期引理”。
A run in a string is a nonextendable (with the same minimal period) periodic segment in a string. The set of runs corresponds to the structure of internal periodicities in a string. Periodicities in strings were extensively studied and are important both in theory and practice (combinatorics of words, pattern-matching, computational biology). Let ρ(n) be the maximal number of runs in a string of length n. It has been shown that ρ(n)=O(n), the proof was very complicated and the constant coefficient in O(n) has not been given explicitly. We demystify the proof of the linear upper bound for ρ(n) and 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)≤3.44n and there are at most O.67n runs with periods larger than 87. This supports the conjecture that the number of all runs is smaller than n. We also give a completely new proof of the linear bound and discover several new interesting “periodicity lemmas”.