Open access
Date
2019Type
- Conference Paper
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. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000351618Publication status
publishedExternal links
Book title
30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)Journal / series
Leibniz International Proceedings in Informatics (LIPIcs)Volume
Pages / Article No.
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für InformatikEvent
Subject
Approximate pattern matching; Lp distance; L1 distance; Hamming distance; Approximation algorithmsMore
Show all metadata