Fast Practical Multi-Pattern Matching

@article{citeulike:1154930, abstract = {The main result of the paper is the construction of a very fast multi-pattern matching algorithm, called DAWG-MATCH. The algorithm is of Boyer-Moore type. Previous algorithm of this type is the Commentz-Walter algorithm. The DAWG-MATCH algorithm behaves better than Commentz-Walter algorithm. We combine the ideas of two algorithms: the Aho-Corasick algorithm, and the Reverse Factor algorithm from Crochemore et alii. The new algorithm performs at most 2jtextj inspections of text characters, and...}, author = {Crochemore, Maxime and Czumaj, Artur and Gasieniec, Leszek and Lecroq, Thierry and Plandowski, Wojciech and Rytter, Wojciech }, citeulike-article-id = {1154930}, journal = {Information Processing Letters}, keywords = {dawg, matching, pattern-matching, string-matching}, number = {3-4}, pages = {107--113}, posted-at = {2007-03-12 06:17:23}, priority = {3}, title = {Fast Practical Multi-Pattern Matching}, url = {http://citeseer.ist.psu.edu/336719.html}, volume = {71}, year = {1999} }

TY - JOUR ID - citeulike:1154930 L3 - citeulike-article-id:1154930 TI - Fast Practical Multi-Pattern Matching JF - Information Processing Letters VL - 71 IS - 3-4 SP - 107 EP - 113 N2 - The main result of the paper is the construction of a very fast multi-pattern matching algorithm, called DAWG-MATCH. The algorithm is of Boyer-Moore type. Previous algorithm of this type is the Commentz-Walter algorithm. The DAWG-MATCH algorithm behaves better than Commentz-Walter algorithm. We combine the ideas of two algorithms: the Aho-Corasick algorithm, and the Reverse Factor algorithm from Crochemore et alii. The new algorithm performs at most 2jtextj inspections of text characters, and... KW - dawg KW - matching KW - pattern-matching KW - string-matching AU - Crochemore, Maxime AU - Czumaj, Artur AU - Gasieniec, Leszek AU - Lecroq, Thierry AU - Plandowski, Wojciech AU - Rytter, Wojciech PY - 1999/// UR - http://citeseer.ist.psu.edu/336719.html ER -