Design and Analysis of String Matching Algorithm on Distributed Memory Machine
Chen Guo · 2000
Parallel string matching algorithms are mainly based on PRAM (parallel random access machine) computation model, while the research on parallel string matching algorithm for other more realistic models is very limited. In this paper, the authors present an efficient and scalable distributed string matching algorithm is presented by parallelizing the improved KMP (Knuth Morris Pratt) algorithm and making use of the pattern period. Its computation complexity is O(n/p+m) and communication time is O(u log p), where n is the length of text, m the length of pattern, p the number of processors and u the period length of pattern.