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

• 作者: 陈倩
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 串匹配 K.M.P.算法 有限自动机
• 年，卷（期）: 2009,（1）
• 所属期刊栏目: 智能、算法、系统结构
• 页码范围: 131-133,138
• 页数: 4页
• 分类号: TP301.6
• 字数: 3200字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2009.01.037

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈倩	华南师范大学物理与电信工程学院	23	51	5.0	6.0