A work-time optimal algorithm for computing all string covers

AbstractIn recent study of repetitive structures of strings, generalized notions 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 prefix 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 superpositions of w. The notion “cover” is a generalization of periods in the sense that superpositions as well as concatenations are considered to define it, whereas only concatenations are considered for periods.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 there is an Ω(log log n) lower bound on the time complexity of the all-covers problem, our algorithm is work-time optimal