摘要： 将有序二叉树和QS算法相结合，提出一种快速多模式字符串匹配算法，实现在多模式匹配过程中不匹配字符的连续跳跃。为提高匹配速度，利用已匹配的字符串信息进行跳跃式的比较，避免文本扫描指针的回溯。实验结果表明，与SMA算法相比，该算法在预处理阶段构造速度和匹配速度更快，在模式串较长的情况下，性能更优越。

关键词: 有序二叉树, 多模式匹配, QS算法

Abstract: This paper combines sequential binary tree with Quick Search(QS) algorithm to propose a fast multi-pattern string matching algorithm, which achieves better performance by shifting unmatched characters continuously in the process of multi-pattern matching. It uses jump comparison with unmatched strings to enhance the speed and decrease character matching operations. Experimental results demonstrate that the algorithm constructs more quickly in preprocessing process and its search speed is higher than SMA algorithm. It achieves better performance in the cases of longer string patterns.

Key words: sequential binary tree, multi-pattern matching, Quick Search(QS) algorithm

中图分类号: 

• TP393