Computing String Covers in Sublinear Time

Let $T$ be a string of length $n$ over an integer alphabet of size $\sigma$. In the word RAM model, $T$ can be represented in $O(n\mathrm{/}{\log }_{\sigma }n)$ space. We show that a representation of all covers of $T$ can be computed in the optimal $O(n\mathrm{/}{\log }_{\sigma }n)$ time; in particular, the shortest cover can be computed within this time. We also design an $O(n(\log \sigma +\log \log n)\mathrm{/}\log n)$-sized data structure that computes in $O(1)$ time any element of the so-called (shortest) cover array of $T$, that is, the length of the shortest cover of any given prefix of $T$. As a by-product, we describe the structure of cover arrays of Fibonacci strings. On the negative side, we show that the shortest cover of a length-$n$ string cannot be computed using $o(n\mathrm{/}\log n)$ operations in the PILLAR model of Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020).