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 repetition, that is, a word composed of exact concatenations of \(u\). In this article we introduce a new notion of \(\alpha \)-partial cover, which can be viewed as a relaxed variant of cover, that is, a factor covering at least \(\alpha \) positions in \(w\). We develop a data structure of \(\mathcal {O}(n)\) size (where \(n=|w|\)) that can be constructed in \(\mathcal {O}(n\log n)\) time which we apply to compute all shortest \(\alpha \)-partial covers for a given \(\alpha \). We also employ it for an \(\mathcal {O}(n\log n)\)-time algorithm computing a shortest \(\alpha \)-partial cover for each \(\alpha =1,2,\ldots ,n\).
cover of a word quasiperiodicity suffix tree