Multiple Patterns Match Algorithm Based on Reverse Finite State Automata
Guo Jun-li · Jisuanji gongcheng · 2010
A fast algorithm to perform multiple patterns match in a string is described.The proposed match algorithm is based on the concept of Deterministic Finite State Automata(DFSA),combining the advantages of Boyer Moore's algorithm,the fast algorithms for single pattern matching.In general,it does not need inspect each character of the string.It skips as many characters as possible by making full use of the succeeded match information and failure information during the matching.The proposed algorithm achieves excellent performance in the cases of both short patterns and long patterns.Experimental results show that in the case of short patterns,the time it takes to search a string is 1/2 of the time DFSA method takes,and in the case of long patterns,the time is only 1/3 of the time by DFSA method.