Parameterized matching with mismatches

The problem of approximate parameterized string searching consists of finding, for a given text t=t1t2…tnt=t1t2…tn and pattern p=p1p2…pmp=p1p2…pm over respective alphabets ΣtΣt and ΣpΣp, the injection πiπi from ΣpΣp to ΣtΣt maximizing the number of matches between πi(p)πi(p) and titi+1…ti+m−1titi+1…ti+m−1(i=1,2,…,n−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+(rp×rt)α(rt)log(rt))O(n+(rp×rt)α(rt)log(rt)), where rprp and rtrt denote the number of runs in the corresponding encodings for y and x, respectively, and α is the inverse of the Ackermann's function.