Closed Repeats

内容摘要

Much research in stringology focuses on structures that can, in a way, ``grasp'' repeats (substrings that occur multiple times) as, for example, the so-called runs, a.k.a. maximal repetitions, compactly describe all tandem repeats. In this paper we introduce closed repeats: given a string $s$, its non-empty substring $s[i\,..\,j]$ is a right (left) closed repeat if its closest occurrence $s[i'\,..\,j']$ with $i' > i$ cannot be ``extended'' to the right (respectively, left) matching $s[j{+}1] = s[j'{+}1]$ (respectively, $s[i{-}1] = s[i'{-}1]$); the repeat is closed if it is both left and right closed. We note that the closed repeats correspond to the maximal closed substrings recently proposed by Badkobeh et al. and they include all runs as a special case. We prove that the number of right/left closed repeats is $O(n \log n)$, where $n$ is the length of $s$, and we show that this bound is tight. The (right/left) closed repeats can be computed in the optimal time $O(n\log n)$; as we prove, the computation time cannot be lower than $Ω(n\logσ)$ over a general ordered alphabet of size $σ$ even when the number of the closed repeats is $O(n)$. As an application, we describe data struct