Pattern matching in multiple streams

We investigate the problem of pattern matching in multiple
streams. In this model, one symbol arrives at a time and is associated with one of s streaming texts. The task at each time step is to report if there is a new match between a fixed pattern of length m and a newly updated stream. As is usual in the streaming context, the goal is to use as little space as possible while still reporting matches quickly. We give matching upper and deterministic space lower bounds for three distinct pattern matching problems. For exact matching we show that the space complexity is $Theta(m + s) words and that new matches can be reported in worst case constant time. For the k-mismatch and k-differences problems we show that the space complexity is Theta(m+ks) and that both problems can be solved in O(k) time per new symbol. Finally we set out a number of open problems related to this new model for pattern matching.