2020/07/27 by Crochemore, Maxime, Iliopoulos, Costas, Radoszewski, Jakub +4
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2007.13471
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.