Fast Algorithm for Partial Covers in Words

A factor u of a word w is a cover of w if every position in w lies within some occurrence of u in w. A word w covered by u thus generalizes the idea of a repitition, that is, a word composed of exact concatenations of u. In this article we introduce a new notion of α-partial-cover, which can be viewed as a relaxed variant of cover, that is, a factor covering at least α positions in w. We develop a data structure of Ο(n) size (where n = |w\) that can be constructed in Ο(n log n) time which apply to computed all shortest α-partial covers for a given α. We also employ it for an Ο(n log n)-time algorithm computing a shortest α-partial cover for each α = 1, 2,...,n.