A Fast String Matching Algorithm Based on Finite Automaton
Chen Qian · Computer Technology and Development · 2009
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 of the state transformation table of the finite automaton to search for the pattern and avoids the backward moving among the failure links when scanning the text,so that the process of pattern matching is more efficient.The analysis in theory and the experiment both indicate that the speed of the algorithm is higher than the K.M.P.algorithm obviously when there are many backward-moving of the failure link when a mismatch occurs locally.However,with respect to the space complexity,the algorithm requires more storage space.