基于混合策略的单模式匹配算法  

Single Pattern Matching Algorithms Based on Hybrid Strategy

作　　者：刘传汉[1] 王永成[1] 刘德荣[1] 李党林[1] 

机构地区：[1]上海交通大学计算机科学与工程系,上海200030

出　　处：《上海交通大学学报》2007年第1期36-41,共6页Journal of Shanghai Jiaotong University

基　　金：国家高技术研究发展规划(863)项目(2002AA119050)

摘　　要：结合后缀有限自动机和正向有限自动机的优点,提出了两个单模式匹配算法.算法中,无论是后缀自动机还是正向有限自动机,只要扫描到的模式前缀长度R>0或者超过模式长度的1/2时,使用正向有限自动机继续向右进行扫描;否则都滑动m-R个字符,使用后缀自动机反向扫描模式串的前缀.两个算法的最差、最好时间复杂度分别为O(n)和O(n/m).结果表明,在短模式的情况下,两个算法的平均时间复杂度均好于RF和LDM,在小字符集长模式或大字符集短模式的情况下它们的平均性能好于BM.Two single pattern matching algorithms by combining a smallest suffix automaton and a forward finite state automaton were presented. Whatever the suffix automaton or the forward finite state automaton is running, the window shifts rn--R characters and then the smallest suffix automaton starts searching the pattern prefixes from right to left if no pattern prefix is found or R is not greater than half of rn, other- wise, the forward finite state automaton starts scanning forwards the corresponding suffixes of the pattern and the new matched prefixes of the pattern is recorded simultaneously. Their time complexities are O（n） in the worst case and O（n/m） in the best case. The experimental results show that their average time complexities are less than that of RF and LDM for short patterns and that of BM for long patterns over small alphabets or short patterns over large alphabets.

关 键 词：模式匹配 LDM算法 后缀自动机 有限状态自动机 时间复杂度 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]