The total run length of a word
A run in a word is a periodic factor whose length is at least twice its period and which cannot be extended to the left or right (by a letter) to a factor with greater period. In recent years a great deal of work has been done on estimating the maximum number of runs that can occur in a word of length n. A number of associated problems have also been investigated. In this paper we consider a new variation on the theme. We say that the total run length (TRL) of a word is the sum of the lengths of the runs in the word and that tau(n) is the maximum TRL over all words of length n. We show that n(2)/8 < tau(n) < 47n(2)/72 + 2n for all n. We also give a formula for the average total run length of words of length n over an alphabet of size alpha, and some other results. Crown Copyright (C) 2013 Published by Elsevier B.V. All rights reserved.
runs words strings