A randomized parallel algorithm for string matching on hypercube

摘要

Given a text of length n and a pattern of length m, a three-phase randomized parallel algorithm for string matching is presented. The parallel algorithm allows the string-matching problem to be solved in O(log n) time on the hypercube network with O(n/log n) processors. It is cost-optimal in the sense that the number of processors times execution time is minimized and the speed-up is maximal. The probability that at least a false match occurs is less than (1.883)kn1 − k/2, where k is the number of repeated times that the derived parallel solver runs on the same input strings.