有限状态自动机及在字符串搜索中的应用

摘要：

有限状态自动机是计算机科学的重要基石，对有限自动机及其应用做了讨论，特别是应用有限自动机描述了简单模式匹配算法及K. M. P.算法，并对K. M. P.算法的时间复杂度进行了较详细的分析。为了应用有限状态自动机解决实际问题，对有限状态自动机的存储结构做了分析，给出了一种高效的有限状态自动机的存储表示，基于这种存储表示，应用确定有限状态自动机可以建立一种效率高于K. M. P.算法的模式匹配算法。使用有限状态自动机建立的算法简单、易懂，且高效，对学生理解掌握有限状态自动机有极大的帮助。

关键词：有限状态自动机、模式匹配、KMP算法

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

资助基金：北京印刷学院精品课程建设项目22150114065

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

页数：共4页

页码：45-47,48