Weighted approximate parameterized string matching
Шибсанкар Дас, Kalpesh Kapoor · AKCE International Journal of Graphs and Combinatorics · 2016
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 m match under weighted Hamming distance in a text of length n. Our main result is an O(nm) time algorithm for this problem. We also investigate string comparison problem with k threshold under weighted Hamming distance and give a O(m+k) time solution. All the above time complexities assume constant size alphabets.