Parameterized matching with mismatches.

The problem of approximate parameterized string searching consists of finding, for a given text t=t"1t"2...t"n and pattern p=p"1p"2...p"m over respective alphabets @S"t and @S"p, the injection @p"i from @S"p to @S"t maximizing the number of matches between @p"i(p) and t"it"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"pxr"t)@a(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 @a is the inverse of the Ackermann's function.