Testing Quasiperiodicity
arXiv:2508.02231 · doi:10.1007/978-3-032-05228-5_1
Abstract
A cover (or quasiperiod) of a string is a shorter string such that every position of is contained in some occurrence of 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 admits a cover. Our tester can also be translated into a streaming algorithm.
To appear at SPIRE 2025