.png){kind=icon}
.png){kind=icon}
Return
Testing Quasiperiodicity
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-05228-5_1.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 cover 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 is an element of [n], epsilon is an element of R+, and oracle access to S, uses O(q(3) epsilon (1) log q) letter queries to test whether S has a cover C of length at most q or is-far from having such a cover. Our insights also lead to a simple streaming algorithm for short covers.
Keywords:
Property testing
Quasiperiodicity
Cover
Seed
Journal
S
IF:
0
Papers:
22
Citations:
0