Saving Space in Fast String-Matching

The string-matching problem is to find all instances (as contiguous substrings) of a “pattern” character string x in a longer “text" string ”. The naive algorithm, trying the pattern from scratch starting at each successive text position, requires only a fixed number of auxiliary storage locations but time proportional to |x|·|Y| (worst case). On the other hand, the fast algorithm of Knuth, Morris, and Pratt requires only time proportional to $|Y|$ but extra space proportional to $|x|$ (every case). Algorithms described in this paper reduce the extra space used by the Knuth–Morris–Pratt algorithm down to O(log |x|), and the time for the naive algorithm down to O(|x|^ε |y|) for any fixed ε > 0. Also described are implementations on two-way multihead finite automata and multitape Turing machines.