Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions

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. >

Authors

• Richard Cole 0001
• Maxime Crochemore
• Zvi Galil
• Leszek Gasieniec
• Ramesh Hariharan
• S. Muthukrishnan 0001
• Kunsoo Park
• Wojciech Rytter

Keywords

• Parallel algorithms
• Pattern matching
• Phase change random access memory
• Educational institutions
• Text processing
• Runtime
• Data structures
• Parallel Algorithm
• Optimization Algorithm
• Time Constant
• Search String
• Simple Algorithm
• Matching Algorithm
• Array Size
• Substring
• Set Position
• Sequential Algorithm
• Top Left Corner
• Euler Number
• 2D Patterns
• Blocks Of Text