[1]陈倩.一种基于有限自动机的快速串匹配算法[J].计算机技术与发展,2009,(01):131-133.
　CHEN Qian.A Fast String Matching Algorithm Based on Finite Automaton[J].,2009,(01):131-133.
点击复制

一种基于有限自动机的快速串匹配算法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2009年01期
页码:
131-133
栏目:
智能、算法、系统工程
出版日期:
1900-01-01

文章信息/Info

Title:
A Fast String Matching Algorithm Based on Finite Automaton
文章编号:
1673-629X（2009）01-0131-03
作者:
陈倩
华南师范大学物理与电信工程学院
Author(s):
CHEN Qian
School of Physics ＆ Telecommunication Engineering, South China Normal University
关键词:
串匹配; K．M．P．算法; 有限自动机
Keywords:
pattern matching; K. M. P. algorithm;  finite automaton
分类号:
TP301.6
文献标志码:
A
摘要:
串匹配是字符串的基本操作之一，因此为它设计一个高效算法具有一定意义。文中基于有限自动机理论，在对经典的K．M．P．算法进行分析的基础上，提出了一种快速的串匹配算法。该算法利用自动机的状态转换表实现串匹配，避免了扫描字符串时的失败链回溯，从而加快了算法的运行速度。理论分析与实验结果均表明，在正文串比较长，模式串中局部匹配失败时失败链反馈较多的情况下，该算法在速度上明显优于K．M．P．算法。但在空间复杂度上，该算法需要较多的存储空间。
Abstract:
Pattern match is one of the basic operations in strings. It is necessary to design an efficient algorithm for it. Brings forward a fast pattern match algorithm based on the K. M. P. algorithm and the finite automaton theory. This algorithm takes advantage

相似文献/References:

[1]孙德才[],王晓霞[]. 近似串匹配过滤算法研究[J].计算机技术与发展,2015,25(04):171.
　SUN De-cai[],WANG Xiao-xia[]. Research on Filtering Algorithm of Approximate String Matching[J].,2015,25(01):171.

备注/Memo

备注/Memo:
广东省自然科学基金资助项目(7005833）陈倩(1975-)，女，浙江杭州人，讲师，博士研究生，研究方向为人工智能。
更新日期/Last Update: 1900-01-01