The number of runs in a string

详细信息    查看全文

• 作者：Wojciech Rytter
• 关键词：Run ; String ; Periodicity
• 刊名：Information and Computation
• 出版年：2007
• 出版时间：September 2007
• 年：2007
• 卷：205
• 期：9
• 页码：1459-1469
• 全文大小：159 K

文摘

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 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”.