论文部分内容阅读
并行串匹配算法的研究大都集中在PRAM(parallel random access machine)模型上，其他更为实际的模型上的并行串匹配算法的研究相对要薄弱得多．该文采用将最优串行算法并行化的技术，利用模式串的周期性质，巧妙地将改进的KMP(Knuth-Morris-Pratt)算法并行化，提出了一个简便、高效且具有良好可扩放性的分布式串匹配算法，其计算复杂度为O(n／P+m)，通信复杂度为O(ulogp)，其中n为文本串长，m为模式串长，u为模式串最小周期长，p为处理器数．