Computing String Covers in Sublinear Time
<|reference_start|>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 /\log_\sigma n)$ space. We show that a representation of all covers of $T$ can be computed in the optimal $O(n/\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)/\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/\log n)$ operations in the PILLAR model of Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020).<|reference_end|>
@article{radoszewski2024computing,
    title={Computing String Covers in Sublinear Time},
    author={Jakub Radoszewski and Wiktor Zuba},
    journal={String Processing and Information Retrieval. SPIRE 2024. Lecture
  Notes in Computer Science, vol. 14899. Springer, Cham},
    year={2024},
    doi={10.1007/978-3-031-72200-4},
    archivePrefix={arXiv},
    eprint={2409.14559},
    primaryClass={cs.DS}
}