模式匹配是计算机应用领域重要的研究方向,广泛应用于入侵检测、信息检索、生物科学计算等方面。随着计算机网络技术的飞速发展,数字信息量出现了爆炸式增长。如何提高模式匹配算法的性能成为人们研究的热门课题。本文介绍了模式匹配技术的产生、发展和研究现状,阐述了几种重要的模式匹配算法,包括单模式匹配BF算法、KMP算法、BM算法、BMH算法、QS算法和KR算法等,多模式匹配AC算法、AC_BM算法、WM算法等,研究分析了它们的时间性能,并比较了各自的优缺点。针对AC_BM算法的不足之处,提出了一种改进的AC_QSS算法。AC_QSS算法采用正向有限状态自动机组织模式串,模式树从右向左移动;每次移动模式树前,检查当前匹配窗口末字符及其后继字符组成的字符串是否出现在模式树中,可以有效提高模式树的平均移动距离,减少不必要的字符比较次数,从而提高算法的时间效率。采用地址映射的方法查找字符串,在预处理阶段将所有模式串的两两相邻字符映射到记录表中,匹配时只需计算偏移地址取值即可完成查找任务,从而进一步提高算法的时间效率。理论分析了AC_QSS算法的时间性能,并通过与AC_BM算法的对比实验,验证了AC_QSS算法具有更好的时间性能。最后对本文进行了总结和展望。