Аннотация:We study a problem of efficient utilisation of extra memory space in real-time string matching. We propose, for any constant ε >0, a real-time string matching algorithm claiming O(m ε ) extra space, where m is the size of a pattern. All previously known real-time string matching algorithms use Ω(m) extra space.