COVERING A STRING

We consider the problem of finding the repetitive structures of a give n string x. The period u of the string x grasps the repetitiveness of x, since x is a prefix of a string constructed by concatenations of u. We generalize the concept of repetitiveness as follows: A string w co vers a string I if there is a superstring of x which is constructed by concatenations and superpositions of Lu. A substring w of x is called a seed of x if w covers x. we present an O (n log n)-time algorithm f or finding all the seeds of a given string of length n.