String Matching in Real Time
Zvi Galil · Journal of the ACM · 1981
A sufficient condition for an on-line algorithm to be transformed into a real-time algorithm is given.This condition is used to construct real-time algorithms for various string-matching problems by random access machines and by Turing machines.