文章基本信息

标题：Generalised Pattern Matching Revisited
本地全文：下载
作者：BartÅ,omiej Dudek ; PaweÅ, Gawrychowski ; Tatiana Starikovskaya 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：154
页码：18:1-18:18
DOI：10.4230/LIPIcs.STACS.2020.18
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In the problem of Generalised Pattern Matching (GPM) [STOC'94, Muthukrishnan and Palem], we are given a text T of length n over an alphabet Î£_T, a pattern P of length m over an alphabet Î£_P, and a matching relationship âS Î£_T Ã- Î£_P, and must return all substrings of T that match P (reporting) or the number of mismatches between each substring of T of length m and P (counting). In this work, we improve over all previously known algorithms for this problem: - For ð'Y being the maximum number of characters that match a fixed character, we show two new Monte Carlo algorithms, a reporting algorithm with time ð'ª(ð'Y n log n log m) and a (1-Îµ)-approximation counting algorithm with time ð'ª(Îµ^-1 ð'Y n log n log m). We then derive a (1-Îµ)-approximation deterministic counting algorithm for GPM with ð'ª(Îµ^-2 ð'Y n logâ¶ n) time. - For ð'® being the number of pairs of matching characters, we demonstrate Monte Carlo algorithms for reporting and (1-Îµ)-approximate counting with running time ð'ª(â^Sð'® n log m â^S{log n}) and ð'ª(â^S{Îµ^-1 ð'®} n log m â^S{log n}), respectively, as well as a (1-Îµ)-approximation deterministic algorithm for the counting variant of GPM with ð'ª(Îµ^-1 â^S{ð'®} n log^{7/2} n) time. - Finally, for â" being the total number of disjoint intervals of characters that match the m characters of the pattern P, we show that both the reporting and the counting variants of GPM can be solved exactly and deterministically in ð'ª(nâ^S{â" log m} +n log n) time. At the heart of our new deterministic upper bounds for ð'Y and ð'® lies a faster construction of superimposed codes, which solves an open problem posed in [FOCS'97, Indyk] and can be of independent interest. To conclude, we demonstrate first lower bounds for GPM. We start by showing that any deterministic or Monte Carlo algorithm for GPM must use Î©(ð'®) time, and then proceed to show higher lower bounds for combinatorial algorithms. These bounds show that our algorithms are almost optimal, unless a radically new approach is developed.
关键词：pattern matching; superimposed codes; conditional lower bounds