Name
Title | ||
|---|---|---|
Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions |
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. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1109/SFCS.1993.366862 | FOCS |
Keywords | Field | DocType |
parallel algorithms,pattern matching,probability,string matching,Las-Vegas algorithm,constant-time text search algorithm,optimally fast parallel algorithms,parallel CRCW PRAM algorithms,pattern matching,preprocessing,probabilistic string-matching algorithm,time bound | String searching algorithm,Log-log plot,Discrete mathematics,Substring,Combinatorics,Open problem,Commentz-Walter algorithm,Parallel algorithm,Computer science,Las Vegas algorithm,Pattern matching | Conference |
ISBN | Citations | PageRank |
0-8186-4370-6 | 34 | 1.65 |
References | Authors | |
9 | 8 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Richard Cole | 1 | 4527 | 505.61 |
| maxime crochemore | 2 | 73 | 6.84 |
| Zvi Galil | 3 | 3634 | 1426.98 |
| L. Gasieniec | 4 | 34 | 1.65 |
| R. Eariharan | 5 | 34 | 1.65 |
| S. Muthukrishnan | 6 | 8025 | 734.98 |
| Kunsoo Park | 7 | 1396 | 171.00 |
| wojciech rytter | 8 | 130 | 17.13 |