2025-09-22
Testing Quasiperiodicity
Publication
Publication
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. We design an algorithm that, given $n = |S|$, $q \in [n]$, $\epsilon \in \mathbb{R}^+$, and oracle access to $S$, uses $\mathcal{O}(q^{3} \epsilon^{-1} \mathrm{log} q)$ letter queries to test whether $S$ has a cover $C$ of length at most $q$ or is $\epsilon$-far from having such a cover. Our insights also lead to a simple streaming algorithm for short covers.
| Additional Metadata | |
|---|---|
| , , , | |
| doi.org/10.1007/978-3-032-05228-5_1 | |
| 32nd International Symposium on String Processing and Information Retrieval, SPIRE 2025 | |
| Organisation | Networks and Optimization |
|
Awofeso, C., Bals, B. J., Lachish, O., & Pissis, S. (2025). Testing Quasiperiodicity. In Proceedings of the International Symposium on String Processing and Information Retrieval (pp. 1–9). doi:10.1007/978-3-032-05228-5_1 |
|
