Fast Algorithm for Partial Covers in Words
Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń · Algorithmica · 2014
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$$ .