Shortest covers of all cyclic shifts of a string (Q5925516)

This paper is concerned with `covers' of strings and their cyclic shifts. For a string \(S\), a factor \(C\) is called a cover if every position in \(S\) is contained in a copy of \(C\). While algorithmically determining the shortest cover of any particular string \(S\) is well known to be solvable in \(\mathcal{O}(n)\) time, this does not immediately lead to an efficient algorithm for determining the shortest cover of each of the cyclic shifts of \(S = S_0 \cdots S_{n-1}\) (that is, all of the strings \(\operatorname{rot}_i(S) = (S_0 \cdots S_{i})^{-1}S(S_0 \cdots S_{i})\) for \(0 \leq i \leq n-1\)). The naive application of the \(\mathcal{O}(n)\)-time algorithm only leads to an \(\mathcal{O}(n^2)\)-time solution for the shortest cover problem for all cyclic shifts. In this work, the authors present a method that solves the shortest cover problem for all cyclic shifts of a string in \(\mathcal{O}(n\log n)\) time. They mention that it is still an open problem if this can be improved to \(\mathcal{O}(n)\) time. If one is only concerned with finding the shortest amongst all of these covers, then they present an algorithm that can do so in \(\mathcal{O}(n)\) time. The main method of proof is based on efficient methods for producing the so-called suffix tree of a string, in which it is efficient to find a shortest cover. The second half of the paper is devoted to establishing an efficient algorithm for the space of Fibonacci strings, defined to be the strings \(\mathrm{Fib}_k\) given by \(\mathrm{Fib}_0 = b\), \(\mathrm{Fib}_1 = a\), and \(\mathrm{Fib}_k = \mathrm{Fib}_{k-1} \mathrm{Fib}_{k-2}\). This is a more detailed exposition of the results announced by the authors in [Lect. Notes Comput. Sci. 12049, 69--80 (2020; Zbl 1495.68251)]. In particular, the authors present a more precise characterisation of shortest covers of cyclic shifts of Fibonacci strings.