Name
Abstract | ||
|---|---|---|
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 $$\\alpha $$¿-partial cover, which can be viewed as a relaxed variant of cover, that is, a factor covering at least $$\\alpha $$¿ 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 $$\\alpha $$¿-partial covers for a given $$\\alpha $$¿. We also employ it for an $$\\mathcal {O}(n\\log n)$$O(nlogn)-time algorithm computing a shortest $$\\alpha $$¿-partial cover for each $$\\alpha =1,2,\\ldots ,n$$¿=1,2,¿,n. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00453-014-9915-3 | Algorithmica |
Keywords | DocType | Volume |
Cover of a word,Quasiperiodicity,Suffix tree | Conference | 73 |
Issue | ISSN | Citations |
1 | 0178-4617 | 1 |
PageRank | References | Authors |
0.35 | 11 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tomasz Kociumaka | 1 | 217 | 38.57 |
| Jakub Radoszewski | 2 | 624 | 50.36 |
| Wojciech Rytter | 3 | 2290 | 181.52 |
| Solon P. Pissis | 4 | 281 | 57.09 |
| Tomasz Waleń | 5 | 706 | 39.62 |