一种基于有限自动机的快速串匹配算法

摘要

串匹配是字符串的基本操作之一,因此为它设计一个高效算法具有一定意义.文中基于有限自动机理论,在对经典的K.M.P.算法进行分析的基础上,提出了一种快速的串匹配算法.该算法利用自动机的状态转换表实现串匹配,避免了扫描字符串时的失败链回溯,从而加快了算法的运行速度.理论分析与实验结果均表明,在正文串比较长,模式串中局部匹配失败时失败链反馈较多的情况下,该算法在速度上明显优于K.M.P.算法.但在空间复杂度上,该算法需要较多的存储空间.