Commentz-Walter algorithm

Uses your system voice; voice and rate in settings.

Snapshot

≈ 1 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1321675524 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001321675524 · captured 1762902646.0 · version history

Cite this page as: encyclopegia.org, “Commentz-Walter algorithm”, snapshot enwiki-001321675524. https://encyclopegia.org/a/commentz-walter-algorithm

Sources cited in this revision

3 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.