Abstract
Quasiperiodicity is a generalization of periodicity that has been researched for almost 30 years. The notion of cover is the classic variant of quasiperiodicity. A cover of a text T is a string whose occurrences in T cover all positions of T. There are several algorithms computing covers of a text in linear time. In this paper we consider a natural extension of cover. For a text T, we call a pair of strings a 2cover if they have the same length and their occurrences cover the text T. We give an algorithm that computes all 2covers of a string of length n in ?(n log n log log n + output) expected time or ?(n log n log² log n / log log log n + output) worstcase time, where output is the size of output.
If (X,Y) is a 2cover of T, then either X is a prefix and Y is a suffix of T, in which case we call (X,Y) a pscover, or one of X, Y is a border (that is, both a prefix and a suffix) of T, and then we call (X,Y) a bcover. A string of length n has up to n pscovers; we show an algorithm that computes all of them in ?(n log log n) expected time or ?(n log² log n / log log log n) worstcase time. A string of length n can have Θ(n²) nontrivial bcovers; our algorithm can report one bcover per length (if it exists) or all shortest bcovers in ?(n log n log log n) expected time or ?(n log n log² log n / log log log n) worstcase time. All our algorithms use linear space.
The problem in scope can be generalized to λ > 2 equallength strings, resulting in the notion of λcover. Cole et al. (2005) showed that the λcover problem is NPcomplete. Our algorithms generalize to λcovers, with (the first component of) the algorithm’s complexity multiplied by n^{λ2}.
BibTeX  Entry
@InProceedings{radoszewski_et_al:LIPIcs:2020:12943,
author = {Jakub Radoszewski and Juliusz Straszyński},
title = {{Efficient Computation of 2Covers of a String}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {77:177:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12943},
URN = {urn:nbn:de:0030drops129432},
doi = {10.4230/LIPIcs.ESA.2020.77},
annote = {Keywords: quasiperiodicity, cover of a string, 2cover, lambdacover}
}
Keywords: 

quasiperiodicity, cover of a string, 2cover, lambdacover 
Collection: 

28th Annual European Symposium on Algorithms (ESA 2020) 
Issue Date: 

2020 
Date of publication: 

26.08.2020 