String covering with optimal covers

In this paper we introduce the notion of an optimal cover. Let M denote the maximum number of positions in w covered by any repeating substring of w . Then a longest (shortest) optimal cover u is a longest (shortest) repeating substring of w that covers M positions. The advantage of this notion is that it is not only applicable to all strings, but also that it does not share the deficiencies of the existing definitions of covers. We show that …