DagSemProc.09281.5.pdf
- Filesize: 276 kB
- 19 pages
Document
Pattern matching with don't cares and few errors
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 9281
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2009-11-10
Cite As Get BibTex
Raphael Clifford, Klim Efremo, Ely Porat, and Amir Rotschild. Pattern matching with don't cares and few errors. In Search Methodologies. Dagstuhl Seminar Proceedings, Volume 9281, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/DagSemProc.09281.5
Abstract
We present solutions for the k-mismatch pattern matching problem with don't cares. Given a text t of length n and a pattern p of length m with don't care symbols and a bound k, our algorithms find all the places that the pattern matches the text with at most k mismatches. We first give an \Theta(n(k + logmlog k) log n) time randomised algorithm which finds the correct answer with high probability. We then present a new deter- ministic \Theta(nk^2 log^m)time solution that uses tools originally developed for group testing. Taking our derandomisation approach further we de- velop an approach based on k-selectors that runs in \Theta(nk polylogm) time. Further, in each case the location of the mismatches at each alignment is also given at no extra cost.
Subject Classification
Keywords
- Prime Numbers
- Group Testing
- Streaming
- Pattern Matching
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads