Springer Verlag, Lecture Notes in Computer Science, p. 177-188
DOI: 10.1007/978-3-642-38905-4_18
Full text: Download
A factor $u$ u of a word $w$ w is a cover of $w$ w if every position in $w$ w lies within some occurrence of $u$ u in $w$ w . A word $w$ w covered by $u$ u thus generalizes the idea of a repetition, that is, a word composed of exact concatenations of $u$ 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$ w . We develop a data structure of $\mathcal {O}(n)$ O(n) size (where $n=|w|$ n=|w| ) that can be constructed in $\mathcal {O}(n\log n)$ O(nlogn) time which we apply to compute all shortest $α $ α -partial covers for a given $α $ α . We also employ it for an $\mathcal {O}(n\log n)$ O(nlogn) -time algorithm computing a shortest $α $ α -partial cover for each $α =1,2,… ,n$ α=1,2,…,n .