Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions
- 1 January 1993
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 248-258
- https://doi.org/10.1109/sfcs.1993.366862
Abstract
All algorithms below are optimal alphabet-independent parallel CRCW PRAM algorithms. In one dimension: Given a pattern string of length m for the string-matching problem, we design an algorithm that computes a deterministic sample of a sufficiently long substring in constant time. This problem used to be a bottleneck in the pattern preprocessing for one- and two-dimensional pattern matching. The best previous time bound was O(log/sup 2/ m/log log m). We use this algorithm to obtain the following results. 1. Improving the preprocessing of the constant-time text search algorithm from O(log/sup 2/ m/log log m) to n(log log m), which is now best possible. 2. A constant-time deterministic string-matching algorithm in the case that the text length n satisfies n=/spl Omega/(m/sup 1+/spl epsiv//) for a constant /spl epsiv/0. 3. A simple probabilistic string-matching algorithm that has constant time with high probability for random input. 4. A constant expected time Las-Vegas algorithm for computing the period of the pattern and all witnesses and thus string matching itself, solving the main open problem remaining in string matching.Keywords
This publication has 18 references indexed in Scilit:
- The Parallel Simplicity of Compaction and ChainingJournal of Algorithms, 1993
- Optimal parallel two dimensional pattern matchingPublished by Association for Computing Machinery (ACM) ,1993
- On a compaction theorem of RagdeInformation Processing Letters, 1992
- A constant-time optimal parallel string-matching algorithmPublished by Association for Computing Machinery (ACM) ,1992
- Truly alphabet-independent two-dimensional pattern matchingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Fast parallel and serial multidimensional approximate array matchingTheoretical Computer Science, 1991
- Optimal parallel suffix-prefix matching algorithm and applicationsPublished by Association for Computing Machinery (ACM) ,1989
- Relations between Concurrent-Write Models of Parallel ComputationSIAM Journal on Computing, 1988
- Efficient randomized pattern-matching algorithmsIBM Journal of Research and Development, 1987
- An O(n log n) algorithm for finding all repetitions in a stringJournal of Algorithms, 1984