In the word RAM model, a string T of length n over an integer alphabet of size σ can be represented in O(n/logσn) space. We show that a representation of all covers of T can be computed in the optimal O(n/logσn) time; in particular, the shortest cover can be computed within this time. We also design an O(n(logσ+loglogn)/logn)-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 the cover array of Fibonacci strings. On the negative side, we show that the shortest cover of a length-n string cannot be computed using o(n/logn) operations in the PILLAR model of Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020).

, , , ,
doi.org/10.1007/978-3-031-72200-4_21
Lecture Notes in Computer Science , International Symposium on String Processing and Information Retrieval
Marie Skłodowska-Curie
31st International Symposium, SPIRE 2024
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Radoszewski, J., & Zuba, W. (2024). Computing string covers in sublinear time. In Proceedings of the International Symposium on String Processing and Information Retrieval (pp. 272–288). doi:10.1007/978-3-031-72200-4_21