Abstract:

For the weakness of low string matching speed, a fast algorithm to perform multiple pattern matching in a string, based on finite state automaton combined with Boyer-Moore(BM) algorithm and an improved quick search(QS) algorithm, was presented. In general, the algorithm described does not need to test each character in the string. By making full use of the results of matching successes and failures, the algorithm can often bypass inspection of as many characters as possible and get all matching locations after one quick search. Experimental results demonstrate that the proposed algorithm has achieved excellent performance in the cases of both short patterns and long patterns and effectively improved the performance of keyword detection and filtering.

Key words: multiple pattern match, finite state automaton, keywords detection and filtering, string