Finite State Machine and Its Application to the String Searching
Cheng Xiaoji · Journal of Beijing Institute of Graphic Communication · 2014
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 automaton. 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.