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

Research on the Performance of Three Suffix Single Pattern Matching Algorithm

分析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.