Constant-Time Randomized Parallel String Matching

. Given a pattern string of length m for the string matching problem, we design an algorithm that computes deterministic samples of a sufficiently long substring of the pattern in constant time. This problem used to be the bottleneck in the pattern preprocessing for one- and two-dimensional pattern matching. The best previous time bound was O(log 2 m= log log m). We use this algorithm to obtain the following results. All algorithms below are optimal parallel algorithms on a CRCW PRAM. 1. A deterministic string-matching algorithm which takes O(log log m) time for preprocessing and constant time for text search, which are the best possible in both preprocessing and text search. 2. A constant-time deterministic string-matching algorithm in the case that the text length n satisfies n = \Omega\Gamma m 1+ffl ) for a constant ffl ? 0. 3. A simple string-matching algorithm that has constant time with high probability for random input. 4. The main result: A constant expected time Las-Vegas..