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 (1995). Taxonomies and Toolkits of Regular Language Algorithms (PDF). Eindhoven, The Netherlands: Eindhoven University of Technology. pp. 53, 116. Archived from the original (PDF) on 2012-03-24. Retrieved 2012-02-15.
  3. ^

External links[edit]