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.

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 |