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
|
Text
AEJ-TCS12-unedited.pdf Download (282kB) | Preview |
Abstract
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 |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 06 Feb 2014 05:35 |
| Last Modified: | 08 Feb 2014 08:03 |
| URI: | http://real.mtak.hu/id/eprint/9905 |
Actions (login required)
 |
Edit Item |
