QS快速单模式匹配的两种改进算法

摘要

模式匹配算法已广泛应用于各个领域,针对如何减少匹配次数,提高算法效率,提出两种改进的QS快速匹配算法.第一种算法通过检测匹配窗口的末字符是否出现于模式串中,并依据情况滑动模式串.第二种算法通过构造BM及QS算法两个坏字符滑动表,经查表比较后确定每一次的滑动距离,使得模式串的滑动距离达到最大,从而大大减少了尝试的次数.实验结果表明,UCD与MSD算法的尝试匹配次数明显优于QS及其他算法,具有更高的效率.