---
title: Commentz-Walter algorithm
slug: commentz-walter-algorithm
qid: 
snapshot: enwiki-001321675524
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1321675524
tags: [30181014]
---

# Commentz-Walter algorithm

> [!note] Provenance
> Snapshot `enwiki-001321675524` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1321675524> · Licensed CC BY-SA 4.0

In computer science, the Commentz-Walter algorithm is a string searching algorithm invented by Beate Commentz-Walter. 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. GNU grep once implemented a string matching algorithm very similar to Commentz-Walter.

In computer science, the Commentz-Walter algorithm is a string searching algorithm invented by Beate Commentz-Walter. 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. GNU grep once implemented a string matching algorithm very similar to Commentz-Walter.
