An improved multi-pattern string matching algorithm

A new algorithm for matching multiple strings at the same time is suggested. The new algorithm is based on the ideas of QS and SunWu algorithm, named as QMS (Quick Multi-pattern Searching) algorithm in this paper. QMS uses hashing and PREFIX table to decrease the number of comparisons. During the computation of the shift distance, the character closely after the current window is considered. Because the shift distance is computed with more accurate technique, larger average shift distance is acquired. More characters can be skipped when the text is scanned, so the algorithm becomes very efficient. Tests on an actual corpus show that QMS algorithm is much more efficient than SunWu algorithm under common circumstances.