Dissemin is shutting down on January 1st, 2025

Published in

Springer Verlag, Lecture Notes in Computer Science, p. 177-188

DOI: 10.1007/978-3-642-38905-4_18

Links

Tools

Export citation

Search in Google Scholar

Fast Algorithm for Partial Covers in Words

This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Green circle
Postprint: archiving allowed
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

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 $α $ α -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 .