A Simple Algorithm for Transposition-Invariant Amplified (δ, γ)-Matching

Inbok LEE  

IEICE TRANSACTIONS on Information and Systems   Vol.E91-D   No.6   pp.1824-1826
Publication Date: 2008/06/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e91-d.6.1824
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Algorithm Theory
combinatorics,  pattern matching,  fast Fourier transform,  

Full Text: PDF>>
Buy this Article

Approximate pattern matching plays an important role in various applications. In this paper we focus on (δ, γ)-matching, where a character can differ at most δ and the sum of these errors is smaller than γ. We show how to find these matches when the pattern is transformed by yx + β, without knowing α and β in advance.