Saving Space in Fast String-Matching
Zvi Galil, Joel Seiferas · SIAM Journal on Computing · 1980
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|\cdot|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|^\varepsilon |y|)$ for any fixed $\varepsilon > 0$. Also described are implementations on two-way multihead finite automata and multitape Turing machines.
Cited by 30 works. doi:10.1137/0209032
Authors
References
- The Design and Analysis of Computer Algorithms
- Fast Pattern Matching in Strings
- On the Computational Complexity of Algorithms
- Guarded commands, nondeterminacy and formal derivation of programs
- The equation $a^M=b^Nc^P$ in a free group.
- On Time Versus Space
- Counter machines and counter languages
- String Matching in Real Time
- Real-time recognition of substring repetition and reversal
- k + 1 Heads Are Better than k