go-v.orgdoi

Saving Space in Fast String-Matching

Zvi Galil, Joel Seiferas · SIAM Journal on Computing · 1980

  • DOI 10.1137/0209032
  • Publisher Society for Industrial and Applied Mathematics
  • Type article
  • Issued 1980

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

SIAM Journal on Computing · Society for Industrial and Applied Mathematics · article · 1980

Abstract

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.

Open the resolved locator · 10.1137/0209032

Metadata licence: OpenAlex metadata (CC0)

Registry
OpenAlex DOI index + API
Fetched
2026-11-20 04:44 UTC
Cache state
not cached yet (bulk-index+openalex)
Locator
https://doi.org/10.1137/0209032
Metadata licence
OpenAlex metadata (CC0)
Scope
Metadata as returned by the resolver; abstracts are never generated here.