On the maximal number of cubic runs in a string

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.

Citation

Crochemore, M. and Iliopoulos, C. and Kubica, M. and Radoszewski, J. and Rytter, W. and Walen, T. 2010. On the maximal number of cubic runs in a string, in Adrian-Horia Dediu, Henning Fernau and Carlos Martin-Vide (ed), 4th International Conference on Language and Automata Theory and Applications, LATA 2010, May 24 2010, pp. 227-238. Trier: Springer.

Source Title

Lecture notes in computer science, volume 6031: language and automata theory and applications - LATA 2010

School

Digital Ecosystems and Business Intelligence Institute (DEBII)

URI

http://hdl.handle.net/20.500.11937/45763

Collection

Curtin Research Publications