Streaming Pattern Matching with Relabelling
Raphaël Clifford, Markus Jalsenius, Benjamin Sach · 2011
We study the problem of pattern matching in a stream where an arbitrary relabelling has been applied to the symbols of the stream. Pattern P of length m is said to match a substring of the stream T at position i if there is an injective (one-to-one) function f such that T[i+j] = f(P[j]) for all 0 6 j < m. Such a mapping corresponds to a relabelling of the symbols and may be distinct for each alignment of the pattern and streaming text. We first present a real-time deterministic algorithm which requires O(|�| +ρ) space, where |�| is the number of distinct characters in the pattern and ρ is the parameterised period of the pattern. We then show how to improve the working space to O(|�|logm) words while still finding all matches under relabelling with high probability. Our improved algorithm can be implemented to run in either O(log|�|) worst case time or expected constant time. Finally we show that the working space is optimal up to logarithmic factors.