Testing Periodicity |
| |
Authors: | Oded Lachish Ilan Newman |
| |
Affiliation: | 1.Department of Computer Science,University of Warwick,Coventry,UK;2.Department of Computer Science,University of Haifa,Haifa,Israel |
| |
Abstract: | We study the string-property of being periodic and having periodicity smaller than a given bound. Let Σ be a fixed alphabet
and let p,n be integers such that
p £ \fracn2p\leq \frac{n}{2}
. A length-n string over Σ, α=(α
1,…,α
n
), has the property Period(p) if for every i,j∈{1,…,n}, α
i
=α
j
whenever i≡j (mod p). For an integer parameter
g £ \fracn2,g\leq \frac{n}{2},
the property Period(≤g) is the property of all strings that are in Period(p) for some p≤g. The property
Period( £ \fracn2)\mathit{Period}(\leq \frac{n}{2})
is also called Periodicity. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|