Real-Time Streaming String-Matching
Dany Breslauer, Zvi Galil · ACM Transactions on Algorithms · 2014
This article presents a real-time randomized streaming string-matching algorithm that uses O (log m ) space. The algorithm only makes one-sided small probability false-positive errors, possibly reporting phantom occurrences of the pattern, but never missing an actual occurrence.