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

摘要

有限状态自动机是计算机科学的重要基石，对有限自动机及其应用做了讨论，特别是应用有限自动机描述了简单模式匹配算法及K. M. P.算法，并对K. M. P.算法的时间复杂度进行了较详细的分析。为了应用有限状态自动机解决实际问题，对有限状态自动机的存储结构做了分析，给出了一种高效的有限状态自动机的存储表示，基于这种存储表示，应用确定有限状态自动机可以建立一种效率高于K. M. P.算法的模式匹配算法。使用有限状态自动机建立的算法简单、易懂，且高效，对学生理解掌握有限状态自动机有极大的帮助。%Finite state machine is an important foundation of computer science, the finite state machine and its application are discussed. The simple pattern matching algorithm and KMP algorithm with finite state machine, and the time complexity of the KMP algorithm are analyzed in detail. In order to apply the finite state machine to solve practical problems, the storage structure of finite state machine is analyzed. An efficient storage structure of finite state machine is constructed. Based on the structure, more efficiency than KMP algorithm of pattern matching algorithm is established using deterministic finite au-tomaton. Algorithms constructed using finite state algorithm is simple, easy to understand, and efficient, and it is help for students to master the finite state automata.