2007 · 18 citations · 13 references
ComputingComputer ScienceData MiningData StructuresParallel AlgorithmsNearest Neighbor SearchSearching AlgorithmsIndexing Data StructuresMatchingMatching AlgorithmsMultiple Pattern MatchingPattern MatchingPattern Matching AlgorithmsPattern SearchingPatterns
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.
13
Basic local alignment search tool
Stephen F. Altschul, Warren Gish, Webb Miller et al. · Journal of Molecular Biology · 1990 · 94.5K citations
Snort - Lightweight Intrusion Detection for Networks
Martin Roesch · 1999 · 3.1K citations
Alfred V. Aho, Margaret J. Corasick · Communications of the ACM · 1975 · 2.9K citations · Full text
A fast string searching algorithm
Robert S. Boyer, J Strother Moore · Communications of the ACM · 1977 · 2.3K citations · Full text
Sun Wu, Udi Manber · Communications of the ACM · 1992 · 734 citations · Full text