Improved multiple patterns string matching algorithm
Libin Yang · Journal of Computer Applications · 2007
Combined with the advantage of the Boyer-Moore-Hoospool (BMH) algorithm, a faster algorithm for performing multiple patterns matching in a string was proposed on the basis of Aho-Corasick (AC) algorithm. In general, it does not need to inspect every character of the string. It skips as many characters as possible to decrease pattern match operations before matching patterns. The proposed algorithm achieves excellent performance in the cases of both short patterns and long patterns. Experimental results show that in case of short patterns the time it takes for the proposed algorithm to search a string is only 50%～30% that of the AC algorithm, while in case of long patterns the ratio is 26.7%～15.2%.