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

• 作者: 林洁 陈国良 顾乃杰
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 串匹配 KMP(Knuth-Morris-Pratt) 分布式算法 可扩放性
• 年，卷（期）: 2000,（6）
• 页码范围: 771-778
• 页数: 8页
• 分类号: TP301
• 字数: 4967字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈国良	中国科学技术大学计算机科学技术系	123	2142	20.0	43.0
2	顾乃杰	中国科学技术大学计算机科学技术系	83	347	9.0	12.0
3	林洁	中国科学技术大学计算机科学技术系	1	24	1.0	1.0