REAL

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

[img] 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.

Item Type: Article
Uncontrolled Keywords: Mismatches; Alphabets; Ackermann's function; Problem solving; Parameterization; Optimization; Encoding (symbols); Binary codes; Approximation theory; String matching; Pattern matching with mismatches; Pattern matching; Parameterized matching; Algorithms
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 06 Feb 2014 09:13
Last Modified: 06 Feb 2014 09:13
URI: http://real.mtak.hu/id/eprint/9915

Actions (login required)

Edit Item Edit Item