Parameterized matching with mismatches

The problem of approximate parameterized string searching consists of finding, for a given text t = t(1)t(2)...t(n) and pattern p = p(1)p(2) ... p(m) over respective alphabets Sigma(t) and Sigma(p), the injection pi(i) from Sigma(p) to Sigma(t) maximizing the number of matches between pi(i)(p) and t(i)t(i+1) ... t(i+m-1) (i = 1, 2 ,..., n-m + 1). We examine the special case where both strings are run-length encoded, and further restrict to the case where one of the alphabets is binary. For this case, we give a construction working in time O(n + (r(p) x r(t)) alpha (r(t)) log(r(t))), where r(p) and r(t) denote the number of runs in the corresponding encodings for y and x, respectively, and alpha is the inverse of the Ackermann's function. (C) 2006 Elsevier B.V. All rights reserved.