Finding the Cyclic Covers of a String

We introduce the concept of cyclic covers, which generalizes the classical notion of covers in strings. Given any nonempty string X of length n, a factor W of X is called a cyclic cover if every position of X belongs to an occurrence of a cyclic shift of W. Two cyclic covers are distinct if one is not a cyclic shift of the other. The cyclic cover problem requires finding all distinct cyclic covers of X. We present an algorithm that solves the cyclic cover problem in time. This is based on finding a well-structured set of standard occurrences of a constant number of factors of a cyclic cover candidate W, computing the regions of X covered by cyclic shifts of W, extending those factors, and taking the union of the results.