Internal Quasiperiod Queries

Abstract

Internal pattern matching requires one to answer queries about factors of a given string. Many results are known on answering internal period queries, asking for the periods of a given factor. In this paper we investigate (for the first time) internal queries asking for covers (also known as quasiperiods) of a given factor. We propose a data structure that answers such queries in $O(\log n\log \log n)$ time for the shortest cover and in $O(\log n(\log \log n{)}^2)$ time for a representation of all the covers, after $O(n\log n)$ time and space preprocessing.

To appear in the SPIRE 2020 proceedings