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]


  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 William (1995-09-15). Taxonomies and toolkits of regular language algorithms. Eindhoven University of Technology. doi:10.6100/IR444299. ISBN 90-386-0396-7.
  3. ^ "src/kwset.c: search for any of a set of keywords". GNU grep. August 1989. Retrieved 2020-07-14.

External links[edit]