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 α-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 O(n) size (where n=|w|) that can be constructed in O(nlogn) time which we apply to compute all shortest α-partial covers for a given α. We also employ it for an O(nlogn)-time algorithm computing a shortest α-partial cover for each α=1,2,…,n.
Original language | English |
---|---|
Pages (from-to) | 217-233 |
Number of pages | 17 |
Journal | Algorithmica |
Volume | 73 |
Issue number | 1 |
DOIs | |
Publication status | Published - 2 Sep 2015 |
Externally published | Yes |
Keywords
- Cover of a word
- Quasiperiodicity
- Suffix tree