文章基本信息
- 标题：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
