STRING MATCHING: A COMPARATIVE STUDY OF ALGORITHMS, AND ITS RELATION TO PROBLEMS OF PARALLEL AND DISTRIBUTED COMPUTING

Our purpose in this work is to provide a comparative study of string matching algorithms and their relationship to problems in parallel and distributed computing. We begin our discussion in chapters one and two with the Knuth-Morris-Pratt and Boyer-Moore algorithms. These optimal serial approaches to string matching provide a reference point against which their parallel counterparts in chapters three through five may be judged. Galil's parallel algorithm in chapter three searches for prefixes of the pattern of increasing length which occur within the text string. Vishkin's Algorithm, described in chapter four employs the concept of duels between various text positions to obtain a sparse set of indices within the text in which the pattern might begin. In chapter five the Rabin-Karp Algorithm is outlined. This approach uses hashing functions called fingerprints, rather than character comparisons, as its basic operation. It is a serial algorithm which unlike other serial approaches is readily parallelizable.; In chapter six we outline an architecture for a parallel processor for Galil's algorithm. The "parallel string processor" (PSP) is an SIMD computer with 2{dollar}sp{lcub}16{rcub}{dollar} PEs and a perfect shuffle interconnection network. In the process of specifying our design we consider sorting algorithms, connection networks, and various paradigms for data broadcasting. Hopefully, this work foreshadows the rapidly unfolding technological breakthroughs that will serve as a bridge to fifth generation systems.