三种后缀单模式匹配算法的性能研究  

Research on the Performance of Three Suffix Single Pattern Matching Algorithm

作　　者：巫喜红[1] WU Xi-hong(School of Computer,Jiaying University,Meizhou 514015,China)

机构地区：[1]嘉应学院计算机学院,广东梅州514015

出　　处：《嘉应学院学报》2018年第5期8-12,共5页Journal of Jiaying University

基　　金：2013年广东省科技计划项目(2013B040500010);2016年广东省重点平台及科研项目(2016KTSCX129);2016年嘉应学院自然科学重点项目(2016KJZ04)

摘　　要：分析Apostolico-Giancarlo(AG)算法、Reverse Colussi(RC)算法和Turbo Reverse Factor(TRF)算法的特点和时间空间复杂度.选取从不同的文本串和模式串,对三种算法进行消耗时间,尝试趟数两方面进行实验.实验结果表明,由于TRF算法采用自动机实现匹配,能大大地缩短匹配时间,因而能更有效地提高模式匹配速度.In this paper,the time and the space complexity of Apostolico-Giancarlo algorithm,Reverse Colussi algorithm and Turbo Reverse Factor algorithm are analyzed.Selecting the different text strings and pattern strings,it carries out the experiments from the time consuming and the numbers of attempts on the three algorithms.The experimental results show that the TRF algorithm can improve the pattern matching speed more effectively because it can shorten the matching time by using automaton to implement matching.

关 键 词：后缀 单模式 AG算法 RC算法 TRF算法 

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