Parameterized searching with mismatches for run-length encoded strings

Apostolico, A. and Erdős, Péter and Jüttner, Alpár (2012) Parameterized searching with mismatches for run-length encoded strings. THEORETICAL COMPUTER SCIENCE, 454. pp. 23-29. ISSN 0304-3975


Download (282kB) | Preview


Parameterized matching between two strings occurs when it is possible to reduce the first one to the second by a renaming of the alphabet symbols. We present an algorithm for searching for parameterized occurrences of a patten in a textstring when both are given in run-length encoded form. The proposed method extends to alphabets of arbitrary yet constant size with O(| rp|×| rt|) time bounds, previously achieved only with binary alphabets. Here rp and rt denote the number of runs in the corresponding encodings for p and t. For general alphabets, the time bound obtained by the present method exhibits a polynomial dependency on the alphabet size. Such a performance is better than applying convolution to the cleartext, but leaves the problem still open of designing an alphabet independent O(| rp|×| rt|) time algorithm for this problem. © 2012 Elsevier B.V. All rights reserved.

Item Type: Article
Uncontrolled Keywords: Pattern matching; Algorithms; Time bound; Time algorithms; String-searching; Run length; Parametric graph; Parameterized; Encodings; Binary alphabets; Alphabet symbols; Alphabet size; String searching; Parametric graph matching; Parameterized matching; Bipartite graphs
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Depositing User: MTMT SWORD
Date Deposited: 06 Feb 2014 05:35
Last Modified: 08 Feb 2014 08:03

Actions (login required)

Edit Item Edit Item