Approximating approximate pattern matching
OPEN ACCESS
Author / Producer
Date
2019
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
Given a text T of length n and a pattern P of length m, the approximate pattern matching problem asks for computation of a particular distance function between P and every m-substring of T. We consider a (1 +/- epsilon) multiplicative approximation variant of this problem, for l_p distance function. In this paper, we describe two (1+epsilon)-approximate algorithms with a runtime of O~(n/epsilon) for all (constant) non-negative values of p. For constant p >= 1 we show a deterministic (1+epsilon)-approximation algorithm. Previously, such run time was known only for the case of l_1 distance, by Gawrychowski and Uznanski [ICALP 2018] and only with a randomized algorithm. For constant 0 <= p <= 1 we show a randomized algorithm for the l_p, thereby providing a smooth tradeoff between algorithms of Kopelowitz and Porat [FOCS 2015, SOSA 2018] for Hamming distance (case of p=0) and of Gawrychowski and Uznanski for l_1 distance.
Permanent link
Publication status
published
External links
Book title
30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)
Volume
128
Pages / Article No.
15
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Approximate pattern matching; Lp distance; L1 distance; Hamming distance; Approximation algorithms