IMPROVED ALGORITHMS FOR MATCHING MULTIPLE PATTERNS

Combined with the advantages of the Quick Search algorithm, a faster algorithm to perform multiple patterns match in a string is put forward on the basis of deterministic finite state automata （DFSA）. Another algorithm is presented with the improvement of the idea of the QS algorithm, and it can match more efficiently. Generally, the two algorithms do not need inspect every character of the string. They skip as many characters as possible by making full use of information in matching failure. The proposed algorithms achieve excellent performance in the cases of both short patterns and long patterns. The actual experiments show that in case of short patterns the time it takes for a proposed algorithm to search a string is only 1/2~1/5 that of the DFSA, while in case of long patterns the ratio is 1/3~1/7.