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

摘要：

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

关键词：串匹配、K.M.P.算法、有限自动机

所属期刊栏目：19

分类号：TP301.6(计算技术、计算机技术)

资助基金：广东省自然科学基金资助项目7005833

在线出版日期：2009-03-31（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：131-133,138