Commentz-Walter algorithm

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In computer science, the Commentz-Walter algorithm is a string searching algorithm invented by Beate Commentz-Walter.[1] Like the Aho–Corasick string matching algorithm, it can search for multiple patterns at once. It combines ideas from Aho–Corasick with the fast matching of the Boyer–Moore string search algorithm. For a text of length n and maximum pattern length of m, its worst-case running time is O(mn), though the average case is often much better.[2]

GNU grep implements a string matching algorithm very similar to Commentz-Walter.[3]

References[edit]

  1. ^ Commentz-Walter, Beate (1979). A String Matching Algorithm Fast on the Average. International Colloquium on Automata, Languages and Programming. LNCS. 71. Graz, Austria: Springer. pp. 118–132. doi:10.1007/3-540-09510-1_10. ISBN 3-540-09510-1. 
  2. ^ Watson, Bruce (1995). Taxonomies and Toolkits of Regular Language Algorithms (PDF). Eindhoven, The Netherlands: Eindhoven University of Technology. pp. 53,116. 
  3. ^ http://git.savannah.gnu.org/cgit/grep.git/tree/src/kwset.c

External links[edit]