A Faster Algorithm for Computing Maximal -gapped Repeats in a String

A string

$$x = uvu$$

with both

u

,

v

being non-empty is called a

gapped repeat with period

$$p = |uv|$$

, and is denoted by pair (

x

,

p

). If

$$p \le \alpha (|x|-p)$$

with

$$\alpha > 1$$

, then (

x

,

p

) is called an

$$\alpha $$

-gapped

repeat. An occurrence

$$[i, i+|x|-1]$$

of an

$$\alpha $$

-gapped repeat (

x

,

p

) in a string

w

is called a

maximal

$$\alpha $$

-gapped repeat of

w

, if it cannot be extended either to the left or to the right in

w

with the same period

p

. Kolpakov et al. (CPM 2014) showed that, given a string of length

n

over a constant alphabet, all the occurrences of maximal

$$\alpha $$

-gapped repeats in the string can be computed in

$$O(\alpha ^2 n + occ )$$

time, where

$$ occ $$

is the number of occurrences. In this paper, we propose a faster

$$O(\alpha n + occ )$$

-time algorithm to solve this problem, improving the result of Kolpakov et al. by a factor of

$$\alpha $$

.