Journal of the ACM Bibliography

Zvi Galil. A constant-time optimal parallel string-matching algorithm. Journal of the ACM, 42(4):908-918, July 1995. [BibTeX entry]

Given a pattern string, we describe a way to preprocess it. We design a CRCW-PRAM constant-time optimal parallel algorithm for finding all occurrences of the (preprocessed) pattern in any given text. Copyright 1995 by ACM, Inc.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- computations on discrete structures

General Terms: Algorithms, Theory

Additional Key Words and Phrases: Constant time, CRCW-PRAM, lion hunting, optimal parallel algorithm, period, string matching

Selected papers that cite this one

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database