2026-08-17T21:01:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8508 2024-03-06T10:42:18Z ddc:004 open_access

Upper and Lower Bounds for Dynamic Data Structures on Strings Clifford, Raphaël Grønlund, Allan Larsen, Kasper Green Starikovskaya, Tatiana exact pattern matching with wildcards hamming distance inner product conditional lower bounds We consider a range of simply stated dynamic data structure problems on strings. An update changes one symbol in the input and a query asks us to compute some function of the pattern of length m and a substring of a longer text. We give both conditional and unconditional lower bounds for variants of exact matching with wildcards, inner product, and Hamming distance computation via a sequence of reductions. As an example, we show that there does not exist an O(m^{1/2-epsilon}) time algorithm for a large range of these problems unless the online Boolean matrix-vector multiplication conjecture is false. We also provide nearly matching upper bounds for most of the problems we consider. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Raphaël Clifford and Allan Grønlund and Kasper Green Larsen and Tatiana Starikovskaya 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.22 urn:nbn:de:0030-drops-85088 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.22 eng https://creativecommons.org/licenses/by/3.0/legalcode