Fast Algorithm for Partial Covers in Words

Abstract

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 $O(n)$ size (where $n=|w|$) that can be constructed in $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 $O(n\log n)$-time algorithm computing a shortest $\alpha$-partial cover for each $\alpha =1,2,\dots ,n$.