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

摘要

在分析Wu-Manber算法的基础上,结合QS算法思想,设计了一种改进的多模式串匹配算法:QWM(quick Wu-Manber).算法充分利用紧邻当前窗口之后的B字符块,使算法的最大移动距离由原来的(m-B+1)增大至(m+B),平均移动距离也得到很大提高.同时对QWM算法和Wu-Manber算法进行了实验对比,无论模式串数量和最小长度怎么变化,性能都有较大提升.实验表明,改进的算法在对英文文本进行扫描时有4%～13%的提高.