Parallel suffix-prefix-matching algorithm and applications

Zvi M. Kedem, Gad M. Landau, Krishna V. Palem

Research output: Contribution to journalArticlepeer-review

Abstract

Our main result in this paper is a parallel algorithm for suffix-prefix- (s-p-) matching that has optimal speedup on a concurrent-read/concurrent-write parallel random-access machine (CRCW PRAM). Given a string of length m, the algorithm runs in time O(log m) using m/ log m processors. This algorithm is important because we utilize s-p matching as a fundamental building block to solve several pattern- and string-matching problems, such as the following: 1. string matching; 2. multitext/multipattern string matching; 3. multidimensional pattern matching; 4. pattern-occurrence detection; 5. on-line string matching. In particular, our techniques and algorithms are the first to preserve optimal speedup in the context of pattern matching in higher dimensions and are the only known ones to do so for dimensions d > 2.

Original languageEnglish (US)
Pages (from-to)998-1023
Number of pages26
JournalSIAM Journal on Computing
Volume25
Issue number5
DOIs
StatePublished - Oct 1996

Keywords

  • Amortized complexity
  • CRCW PRAMs
  • Multidimensional pattern matching
  • Parallel algorithms
  • Pattern-matching automaton
  • Speedup
  • String matching

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Parallel suffix-prefix-matching algorithm and applications'. Together they form a unique fingerprint.

Cite this