2026-07-26T00:57:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10486 2024-03-06T10:45:51Z ddc:004 open_access

Approximating Approximate Pattern Matching Studený, Jan Uznański, Przemysław Approximate Pattern Matching l_p Distance l_1 Distance Hamming Distance Approximation Algorithms 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 Uznański [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 Uznański for l_1 distance. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jan Studený and Przemysław Uznański 2019 Is Part Of LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2019.15 urn:nbn:de:0030-drops-104865 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.15 eng https://creativecommons.org/licenses/by/3.0/legalcode