一种改进的多模式串匹配算法

摘要

在对著名的 SunWu 多模式串匹配算法进行分析之后,结合 QS 算法的优点,设计了一种较高效的多模式串匹配算法 QMS.该算法使用散列技术和前缀表减少发生部分匹配时实际进行的模式串比较次数.在计算跳跃距离时,充分考虑当前窗口紧邻的下一个字符带来的信息,使用更加精确的跳跃距离计算方法以获得更大的平均跳跃距离,从而获得更高的扫描效率和空间利用率.在真实文本上的对比实验表明,在通常应用环境中,该算法缩短了扫描时间,取得了较好的效果.