###
Average-Optimal Single and Multiple Approximate String Matching

####
Kimmo Fredriksson and Gonzalo Navarro

We present a new algorithm for multiple approximate string matching. It is
based on reading backwards enough *l*-grams from text windows so as to
prove that no occurrence can contain the part of the window read, and then
shifting the window.
We show analytically that our algorithm is optimal on average. Hence our first
contribution is to fill an important gap in the area, since no average-optimal
algorithm existed for multiple approximate string matching.

We consider several variants and practical improvements to our algorithm, and
show experimentally that they are resistant to the number of patterns and the
fastest for low difference ratios, displacing the long-standing best algorithms.
Hence our second contribution is to give a practical algorithm for this problem,
by far better than any existing alternative in many cases of interest.
On real life texts, our algorithm is especially interesting for computational
biology applications.

In particular, we show that our algorithm can be successfully used to search
for one pattern, where many more competing algorithms exist. Our algorithm is
also average-optimal in this case, being the second after that of Chang and
Marr. However, our algorithm permits higher difference ratios than Chang and
Marr, and this is our third contribution.

In practice, our algorithm is competitive in this scenario too, being the
fastest for low difference ratios and moderate alphabet sizes. This is our
fourth contribution, which also answers affirmatively the question of whether
a practical average-optimal approximate string matching algorithm existed.