Parameterized matching with mismatches

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