2021/07/09 by Tung Mai, Mai, Tung, Anup Rao +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2107.04660
openalex publication_date 2021/07/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this work, we study longest common substring, pattern matching, and wildcard pattern matching in the asymmetric streaming model. In this streaming model, we have random access to one string and streaming access to the other one. We present streaming algorithms with provable guarantees for these three fundamental problems. In particular, our algorithms for pattern matching improve the upper bound and beat the unconditional lower bounds on the memory of randomized and deterministic streaming algorithms. In addition to this, we present algorithms for wildcard pattern matching in the asymmetric streaming model that have optimal space and time.