Computing the covers of a string in linear time

The paper presents covers and their generalizations with their potential applications in DNA sequence analysis. The characterization of all covers of x in terms of an easily computed normal form for x is discussed. The characterization theorem then gives rise to a simple recursive algorithm which computes all the covers of x in time. The results of this paper are also applicable to a problem studied by Apostolico and Ehrenfeucht; the computation of all substrings of x which have a proper cover.