Approximate pattern matching plays an important role in various applications, such as bioinformatics, computer-aided music
analysis and computer vision. We focus on (δ, γ)-matching. Given a text T of length n, a pattern P of length m,and two parameters δ and γ, the aim is to find all the substring T[i, i+m–1] such that (a) ∀ 1 ≤ j ≤ m, |T[i+j–1] – P[j]| ≤ δ (δ-matching) , and (b) ∑1 ≤ j ≤ m |T[i+j–1] – P[j]| ≤ γ (γ-matching). In this paper we consider three variations of (δ, γ)-matching: amplified matching, transposition-invariant matching, and amplified transposition-invariant matching. For each problem we propose a simple and efficient algorithm which is easy to implement.
This research was supported by the MIC(Ministry of Information and Communication), Korea, under the ITRC(Information Technology
Research Center) support program supervised by the IITA(Institute of Information Technology Assessment).