基于划分的模式匹配改进算法

摘要：

为提高基于划分窗口的字符串匹配算法(SKIP和KMPSKIP算法)的性能,结合QS算法的优点,通过提前预览下一窗口最后一个字符的移动信息跳过尽可能多的字符进行下一轮匹配,减少了匹配次数,提高了匹配效率.理论分析及实验结果均表明,改进算法在平均时间复杂度方面优于原始算法,在模式较短的情况下,ISKIP算法的平均运行时间仅为BMH算法的65%～85%.

关键词：模式匹配、快速搜索算法、划分窗口、时间复杂度

所属期刊栏目：34

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家高技术研究发展计划863计划2006AA01Z431;浙江省科技计划2006C21028;澳门科技基金005/2006/A;浙江省重大科技专项重点项目2006C11105

在线出版日期：2008-05-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：41-44