Parameterized matching with mismatches

Apostolico, Alberto and Erdős, Péter and Lewenstein, Moshe (2007) Parameterized matching with mismatches. JOURNAL OF DISCRETE ALGORITHMS, 5 (1). pp. 135-140. ISSN 1570-8667

Text param-match-Final.pdf Restricted to Repository staff only Download (175kB) | Request a copy

Abstract

The problem of approximate parameterized string searching consists of ¯nding, 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.

Actions (login required)

Edit Item