A WORK-TIME OPTIMAL ALGORITHM FOR COMPUTING ALL STRING COVERS

In recent study of repetitive structures of strings, generalized notio ns of periods have been introduced. A typical regularity, the period u of a given string x, grasps the repetitiveness of x since x is a pref ix of a string constructed by concatenations of u. A substring w of x is called a cover of x if x can be constructed by concatenations and s uperpositions of w. The notion ''cover'' is a generalization of period s in the sense that superpositions as well as concatenations are consi dered to define it, whereas only concatenations are considered for per iods. We consider the all-covers problem, i.e., that of computing all the covers of a given string of length n. We present an optimal O(log log n)-time CRCW PRAM algorithm for the all-covers problem. Since ther e is an Omega(log log n) lower bound on the time complexity of the all -covers problem, our algorithm is work-time optimal.