AbstractGiven 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
- Maxime Crochemore, Zvi Galil, Leszek G\c{a}sieniec, Kunsoo Park, and Wojciech Rytter. Constant-time randomized parallel string matching. SIAM Journal on Computing, 26(4):950-960, August 1997.
Selected references
- Richard P. Brent. The parallel evaluation of general arithmetic expressions. Journal of the ACM, 21(2):201-206, April 1974.
- Dany Breslauer and Zvi Galil. A lower bound for parallel string matching. In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 439-443, New Orleans, Louisiana, 6-8 May 1991.
- Richard Cole, Maxime Crochemore, Zvi Galil, Leszek G\c{a}sieniec, Ramesh Hariharan, S. Muthukrishnan, Kunsoo Park, and Wojceich Rytter. Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions. In 34th Annual Symposium on Foundations of Computer Science, pages 248-258, Palo Alto, California, 3-5 November 1993. IEEE.
- Artur Czumaj, Zvi Galil, Leszek G\c{a}sieniec, Kunsoo Park, and Wojciech Plandowski. Work-time-optimal parallel algorithms for string problems. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 713-722, Las Vegas, Nevada, 29 May-1 June 1995.
- Zvi Galil. Optimal parallel algorithms for string matching. Information and Control, 67(1-3):144-157, October/November/December 1985.
- Richard M. Karp, Raymond E. Miller, and Arnold L. Rosenberg. Rapid identification of repeated patterns in strings, trees and arrays. In Conference Record, Fourth Annual ACM Symposium on Theory of Computing, pages 125-136, Denver, Colorado, 1-3 May 1972.
- Uzi Vishkin. Optimal parallel pattern matching in strings. Information and Control, 67(1-3):91-113, October/November/December 1985.