Fast Parallel String Prefix-Matching

Abstract

An 0(loglogm) time nlogm/loglogm-processor CRCW-PRAM algorithm for the string prefix-matching problem over a general alphabet is presented. The algorithm can also be used to compute the KMP failure function in 0(loglogm) time on mlogm/loglogm processors. These results improve on the running time of the best previous algorithm for both problems, which was 0 (log m), while preserving the same number of operations.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1992
Accession Number
ADA267758

Entities

People

  • Dany Breslauer

Organizations

  • Columbia University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Alphabets
  • Arithmetic
  • Boundaries
  • Computations
  • Mathematical Analysis
  • Mathematics
  • Notation
  • Periodic Variations
  • Sequences
  • Text Processing

Fields of Study

  • Computer science

Readers

  • Computer Programming and Software Development.
  • Parallel and Distributed Computing.