分布式存储的并行串匹配算法的设计与分析

并行串匹配算法的研究大都集中在pram(parallelrandomaccessmachine)模型上,其他更为实际的模型上的并行串匹配算法的研究相对要薄弱得多.该文采用将最优串行算法并行化的技术,利用模式串的周期性质,巧妙地将改进的kmp(knuth-morris-pratt)算法并行化,提出了一个简便、高效且具有良好可扩放性的分布式串匹配算法,其计算复杂度为o(n/p+m),通信复杂度为o(ulogp