Abstract

(?,?)-Matching is a string matching problem with applications to music retrieval. The goal is, given a pattern P1...m and a text T1...n on an alphabet of integers, find the occurrences P' of the pattern in the text such that (i) ?1 ? i ? m, |Pi - Pi? ? ?, and (ii) ?1?i?m |Pi - Pi| ? ?. Several techniques for (?,?)-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 ? and ?. We implemented our algorithm and drew experimental results on real music showing that our algorithm is superior to current alternatives. © Springer-Verlag Berlin Heidelberg 2003.