  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.
