Faster parallel string matching via larger deterministic samples. (English) Zbl 0797.68083

Goldberg, Tal; Zwick, Uri

J. Algorithms 16, No. 2, 295-308 (1994).

Summary: Building on previous results of Breslauer, Galil, and Vishkin, we obtain for every \(p(m)= \Omega (\log\log m)\) an optimal speedup parallel string matching algorithm that can preprocess a pattern \(P\) of length \(m\) in time \(O(p(m))\) and can then find all occurrences of \(P\) in a text of an arbitrary length in time \(O(\log\log m/\log p(m))\). Letting \(p(m)= (\log m)^ \varepsilon\), for any \(\varepsilon>0\), we obtain a constant \(O(1/\varepsilon)\) search time. Letting \(p(m)= \log\log m\) we obtain a search time of \(O(\log\log m/ \log\log \log m)\). The first result improves the preprocessing time of Galil’s constant time algorithm. The second result improves the search time of Breslauer’s and Galil’s \(O(\log\log m)\) time algorithm. The main ingredient used to obtain this trade-off is a new algorithm for the computation of deterministic samples of superlogarithmic size in sublogarithmic time. This algorithm generalizes a similar algorithm recently obtained by Crochemore, Gąsieniec, Rytter, Muthukrishnan, and Ramesh. We also show that in the parallel comparison model, the search can be performed in constant time after \(O(\log\log m)\) preprocessing rounds using an optimal number of comparisons. This completely matches a lower bound of Breslauer and Galil.

MSC:

68Q25	Analysis of algorithms and problem complexity
68W15	Distributed algorithms
68P10	Searching and sorting

Keywords:

optimal speedup parallel string matching algorithm