Algorithms on Extended (δ, γ)-Matching

Inbok Lee, Raphaël Clifford, Kim Sung-Kyul

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

3 Citations (Scopus)


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 ≤ jm, |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).

Translated title of the contributionAlgorithms on Extended (delta, gamma)-Matching
Original languageEnglish
Title of host publicationComputational Science and Its Applications - ICCSA 2006
Subtitle of host publicationInternational Conference, Glasgow, UK, May 8-11, 2006. Proceedings, Part II
Number of pages6
ISBN (Electronic)9783540340744
ISBN (Print)9783540340720
Publication statusPublished - 2006

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743

Bibliographical note

ISBN: 03029743
Publisher: Springer Berlin/Heidelberg
Name and Venue of Conference: International Conference on Computational Science and its Applications (ICCSA 2006)
Other identifier: 2000603


Dive into the research topics of 'Algorithms on Extended (δ, γ)-Matching'. Together they form a unique fingerprint.

Cite this