2025/08/04 by Awofeso, Christine, Bals, Ben, Lachish, Oded +1
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2508.02231
A cover (or quasiperiod) of a string S is a shorter string C such that every position of S is contained in some occurrence of C as a substring. The notion of covers was introduced by Apostolico and Ehrenfeucht over 30 years ago [Theor. Comput. Sci. 1993] and it has received significant attention from the combinatorial pattern matching community. In this note, we show how to efficiently test whether S admits a cover. Our tester can also be translated into a streaming algorithm.