Average-Case Optimal Approximate Circular String Matching

Approximate string matching is the problem of finding all factors of a text

$$t$$

of length

$$n$$

that are at a distance at most

$$k$$

from a pattern

$$x$$

of length

$$m$$

. Approximate circular string matching is the problem of finding all factors of

$$t$$

that are at a distance at most

$$k$$

from

$$x$$

or

from any of its rotations. In this article, we present a new algorithm for approximate circular string matching under the edit distance model with optimal average-case search time

$$\mathcal {O}(n(k + \log m) /m)$$

. Optimal average-case search time can also be achieved by the algorithms for multiple approximate string matching (Fredriksson and Navarro, 2004) using

$$x$$

and its rotations as the set of multiple patterns. Here we reduce the preprocessing time and space requirements compared to that approach.