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

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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(log2 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(log2 m/log log m) to O(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 = Ω(m1+ε) for a constant ε>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. In two dimensions: Given an m×m pattern, we present the first optimal alphabet-independent parallel algorithm for two-dimensional pattern matching which requires constant-time text processing following O(log log m)-time preprocessing of the pattern. This algorithm depends upon three new time- and work-optimal results, one of which is the constant-time deterministic sample computation above. The second is a simple constant-time two-dimensional pattern matching algorithm, given a deterministic sample and two-dimensional witnesses. The best previous optimal two-dimensional text search takes O(log log m) time. The third is an O(log log m)-time algorithm that computes two-dimensional witnesses. No optimal parallel algorithm was known before. The best previous algorithm takes O(log m) time and uses O(m2 log m) operations and more than linear space.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundatons of Computer Science (Proceedings)
Editors Anon
PublisherPubl by IEEE
Pages248-258
Number of pages11
ISBN (Print)0818643706
StatePublished - 1993
EventProceedings of the 34th Annual Symposium on Foundations of Computer Science - Palo Alto, CA, USA
Duration: Nov 3 1993Nov 5 1993

Publication series

NameAnnual Symposium on Foundatons of Computer Science (Proceedings)
ISSN (Print)0272-5428

Other

OtherProceedings of the 34th Annual Symposium on Foundations of Computer Science
CityPalo Alto, CA, USA
Period11/3/9311/5/93

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions'. Together they form a unique fingerprint.

Cite this