Weighted approximate parameterized string matching

Abstract

We consider the problem of finding a bijection to match a pattern in a text where both the pattern and the text are strings from distinct alphabets. The objective of weighted approximate parameterized string matching problem is to find approximate parameterized pattern of length match under weighted Hamming distance in a text of length . Our main result is an time algorithm for this problem. We also investigate string comparison problem with threshold under weighted Hamming distance and give a time solution. All the above time complexities assume constant size alphabets.

Keywords

• weighted hamming distance
• approximate string matching
• parameterized matching
• maximum weight bipartite matching