Can I read Searching of Gapped Repeats and Subrepetitions in a Word on EtoBox?

Searching of Gapped Repeats and Subrepetitions in a Word by Kolpakov, Roman; Podolskiy, Mikhail; Posypkin, Mikhail; Khrapov, Nickolay is a scholarly article available to read on EtoBox.

What is Searching of Gapped Repeats and Subrepetitions in a Word about?

A gapped repeat is a factor of the form $uvu$ where $u$ and $v$ are nonempty words. The period of the gapped repeat is defined as $|u|+|v|$. The gapped repeat is maximal if it cannot be extended to the left or to the right by at least one letter with preserving its period. The gapped repeat is called $\alpha$-gapped if its period is not greater than $\alpha |v|$. A $\delta$-subrepetition is a factor which exponent is less than 2 but is not less than $1+\delta$ (the exponent of the factor is the quotient of the length and the minimal period of the factor). The $\delta$-subrepetition is maximal if it cannot be extended to the left or to the right by at least one letter with preserving its minimal period. We reveal a close relation between maximal gapped repeats and maximal subrepetitions. Moreover, we show that in a word of length $n$ the number of maximal $\alpha$-gapped repeats is bounded by $O(\alpha^2n)$ and the number of maximal $\delta$-subrepetitions is bounded by $O(n/\delta^2)$. Using the obtained upper bounds, we propose algorithms for finding all maximal $\alpha$-gapped repeats and all maximal $\delta$-subrepetitions in a word of length $n$. The algorithm for finding all m

Author

Kolpakov, Roman; Podolskiy, Mikhail; Posypkin, Mikhail; Khrapov, Nickolay

Published

2013

Language

EN