Efficient (δ, γ)-pattern-matching with don’t cares

Here we consider string matching problems that arise naturally in applications to music retrieval. The δ-Matching problem calculates, for a given text T1..n and a pattern P1..m on an alphabet of integers, the list of all indices Iδ = {1 ≤ i ≤ n−m+1: max m j=1 |Pj−Ti+j−1 | ≤ δ}. The γ-Matching problem computes, for given T and P, the list of all indices Iγ = {1 ≤ i ≤ n −m + 1: Pm j=1 |Pj − Ti+j−1 | ≤ γ}. In this paper, we extend the current result on the different matching problems to handle the presence of “don’t care ” symbols. We present efficient algorithms that calculate Iδ, Iγ, and I(δ,γ) = Iδ∩Iγ, for pat-tern P with occurrences of “don’t cares”