###
A Bit-parallel Suffix Automaton Approach
for *(delta,gamma)*-Matching in Music Retrieval

####
Maxime Crochemore, Costas Iliopoulos, Gonzalo Navarro and Yoan Pinzón

*(delta,gamma)*-Matching is a string matching problem with
applications to music retrieval. The goal is, given a pattern
*P[1...m]* and a text *T[1...n]* on an alphabet of
integers, find the occurrences *P'* of the pattern in the text
such that (i) *for all 1<=i<=m, |P[i]-P'[i]| <= delta*, and
(ii) *sum(1<=i<=m) |P[i]-P'[i]| <= gamma*. Several
techniques for *(delta,gamma)*-matching have been proposed. In
this paper we show that a classical string matching technique that
combines bit-parallelism and suffix automata can be successfully
adapted to this problem. This is the first character-skipping
algorithm that skips characters using both *delta* and *gamma*.
We implemented our algorithm and drew experimental results on real
music showing that our algorithm is superior to current
alternatives.