On the maximal number of cubic runs in a string
MetadataShow full item record
A run is an inclusion maximal occurrence in a string (as a subinterval) of a repetition v with a period p such that 2p =|v|.The maximal number of runs in a string of length n has been thoroughly studied, and is known to be between 0.944 n and 1.029 n.In this paper we investigate cubic runs, in which the shortest period p satis?es 3p =|v|. We show the upper bound of 0.5 n on the maximal number of such runs in a string of length n, and construct an in?nite sequence of words over binary alphabet for which the lower bound is 0.406 n.
Showing items related by title, author, creator and subject.
Crochemore, M.; Iliopoulos, Costas; Pissis, S.; Tischler, G. (2010)A proper fact or u of a string y is a cover of y if every letter of y is within some occurrence of u in y. The concept generalises the notion of periods of a string. An integer array C is the minimal-cover (resp. ...
Selected Physical Characteristics and Playing-Related Musculoskeletal Problems in Adolescent String InstrumentalistsVinci, S.; Smith, A.; Ranelli, Sonia (2015)PURPOSE: Music research has investigated the prevalence of playing-related musculoskeletal problems in adults and children, but the prevalence in adolescents has not been established. String instrumentalists report high ...
Iliopoulos, Costas; Smyth, Bill; Yusufu, M. (2009)A repeat in a string is a substring that occurs more than once. A repeat is extendible if every occurrence of the repeat has an identical letter either on the left or on the right; otherwise, it is maximal. A multirepeat ...