论文部分内容阅读
串匹配是计算机科学中一个基本、重要的研究问题,它在Internet网络信息搜索、生物信息学、网络入侵检测、网络远程教育、电子商务等领域具有广泛的应用.该文围绕精确串匹配、多模式串匹配、近似串匹配、近似词典匹配和扩展的最长公共于序列问题开展研究,主要内容、贡献和创新包括:(1)基于孙子定理和karp—Rabin模式匹配思想的确定性串匹配算法及其并行化.(2)基于映射和Hashing的多模式串匹配及具并行算法.(3)PRAM 模型上代价最优的允许k-差别的近似串匹配并行算法和LARPBS模型上常数时间的允许k-误配的近似串匹配并行算法.(4)允许k-差别的可变长模式串近似词典匹配及其在PRAM和BSR模型上的并行处理.(5)基于SMP Clusters 的扩展最长公共子序列问题的并行计算.