Computing string covers in sublinear time

Let T be a string of length n over an integer alphabet of size σ. In the word RAM model, T 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 com- puted within this time. We also design an O(n(log σ + 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)

• View at arXiv

Free Full Text ( Final Version , 218kb )