2026-07-22T00:14:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12140 2024-03-06T10:49:24Z ddc:004 open_access

The Streaming k-Mismatch Problem: Tradeoffs Between Space and Total Time Golan, Shay Kociumaka, Tomasz Kopelowitz, Tsvi Porat, Ely Streaming pattern matching Hamming distance k-mismatch We revisit the k-mismatch problem in the streaming model on a pattern of length m and a streaming text of length n, both over a size-σ alphabet. The current state-of-the-art algorithm for the streaming k-mismatch problem, by Clifford et al. [SODA 2019], uses Õ(k) space and Õ(√k) worst-case time per character. The space complexity is known to be (unconditionally) optimal, and the worst-case time per character matches a conditional lower bound. However, there is a gap between the total time cost of the algorithm, which is Õ(n√k), and the fastest known offline algorithm, which costs Õ(n + min(nk/√m, σn)) time. Moreover, it is not known whether improvements over the Õ(n√k) total time are possible when using more than O(k) space. We address these gaps by designing a randomized streaming algorithm for the k-mismatch problem that, given an integer parameter k≤s≤m, uses Õ(s) space and costs Õ(n+min(nk²/m, nk/√s, σnm/s)) total time. For s=m, the total runtime becomes Õ(n + min(nk/√m, σn)), which matches the time cost of the fastest offline algorithm. Moreover, the worst-case time cost per character is still Õ(√k). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shay Golan and Tomasz Kociumaka and Tsvi Kopelowitz and Ely Porat 2020 Is Part Of LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2020.15 urn:nbn:de:0030-drops-121406 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.15 eng https://creativecommons.org/licenses/by/3.0/legalcode