An optimal algorithm to compute all the covers of a string

Let x denote a given nonempty string of length n = |x| ⩾ 1. A string u is a cover of x if and only if every position of x lies within an occurrence of u within x. Thus x is always a cover of itself. In this paper we characterize all the covers of x in terms of an easily computed normal form for x. The characterization theorem then gives rise to a simple recursive algorithm which computes all the covers of x in time Θ(n).