  Quasiperiodicity in strings was introduced almost 30 years ago as an
extension of string periodicity. The basic notions of quasiperiodicity are
cover and seed. A cover of a text $T$ is a string whose occurrences in $T$
cover all positions of $T$. A seed of text $T$ is a cover of a superstring of
$T$. In various applications exact quasiperiodicity is still not sufficient due
to the presence of errors. We consider approximate notions of quasiperiodicity,
for which we allow approximate occurrences in $T$ with a small Hamming,
Levenshtein or weighted edit distance.
  In previous work Sip et al. (2002) and Christodoulakis et al. (2005) showed
that computing approximate covers and seeds, respectively, under weighted edit
distance is NP-hard. They, therefore, considered restricted approximate covers
and seeds which need to be factors of the original string $T$ and presented
polynomial-time algorithms for computing them. Further algorithms, considering
approximate occurrences with Hamming distance bounded by $k$, were given in
several contributions by Guth et al. They also studied relaxed approximate
quasiperiods that do not need to cover all positions of $T$.
  In case of large data the exponents in polynomial time complexity play a
crucial role. We present more efficient algorithms for computing restricted
approximate covers and seeds. In particular, we improve upon the complexities
of many of the aforementioned algorithms, also for relaxed quasiperiods. Our
solutions are especially efficient if the number (or total cost) of allowed
errors is bounded. We also show NP-hardness of computing non-restricted
approximate covers and seeds under Hamming distance.
  Approximate covers were studied in three recent contributions at CPM over the
last three years. However, these works consider a different definition of an
approximate cover of $T$.
