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

摘要

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 y = αx + β, without knowing α and β in advance.