Constant-time randomized parallel string matching. (English) Zbl 0885.68078

Crochemore, Maxime; Galil, Zvi; Gasieniec, Leszek; Park, Kunsoo; Rytter, Wojciech

SIAM J. Comput. 26, No. 4, 950-960 (1997).

Summary: 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 2m \log \log m)\). We use this algorithm to obtain the following results (all algorithms below are optimal parallel algorithms on a CRCW PRAM):
– 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;
– a constant-time deterministic string-matching algorithm in the case, where the text length \(n\) satisfies \(n= \Omega(m^{1+\varepsilon})\) for a constant \(\varepsilon>0\);
– a simple string-matching algorithm that has constant time with high probability for random input;
– the main result: a constant-expected-time Las Vegas algorithm for computing the period of the pattern and all witnesses and thus for string matching itself; in both cases, an \(\Omega(\log\log m)\) lower bound is known for deterministic algorithms.

MSC:

68W15	Distributed algorithms
68Q25	Analysis of algorithms and problem complexity
68R15	Combinatorics on words

Keywords:

parallel string matching; randomized algorithms; deterministic samples