Multiple Skip Multiple Pattern Matching Algorithm (MSMPMA)
Musbah M. Aqel, M M Ibrahiem · 2007
A new algorithm to search for multiple patterns simultaneously is proposed. The multiple pattern algorithms can be used in many applications that require such type of search and matching. For example, a multi- pattern matching can be used in lieu of indexing or sorting data in some applications that involve small to medium size datasets. One of its advantages is that no additional search structure is needed and no preprocessing phase is required. The proposed algorithm is simple and can suit for multiple patterns matching in a file with unlimited size. The time complexity of the algorithm is O (n*m), but because of the skips it moves to around O (n). The number of comparisons rapidly decreased after the first match, and for multiple matching, it will be little greater than n (file size). The algorithm was implemented and compared with some popular multi-pattern matching algorithms and it has shown more enhancement in performance and faster than others.