Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Commentz-Walter algorithm
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, the Commentz-Walter algorithm is a <a href="/facts/String_searching_algorithm/RCvwDRle">string searching algorithm</a> invented by Beate Commentz-Walter. Like the <a href="/facts/Aho%E2%80%93Corasick_string_matching_algorithm/huUFNcv8">Aho–Corasick string matching algorithm</a>, it can search for multiple patterns at once. It combines ideas from Aho–Corasick with the fast matching of the <a href="/facts/Boyer%E2%80%93Moore_string-search_algorithm/yUGSAvN6">Boyer–Moore string-search algorithm</a>. For a text of length <i>n</i> and maximum pattern length of <i>m</i>, its worst-case running time is <a href="/facts/Big-O_notation/weFFjSWg">O</a>(<i>mn</i>), though the average case is often much better. </p><p><a href="/facts/GNU/HlAKKBdt">GNU</a> <a href="/facts/Grep/PdGQeFfD">grep</a> once implemented a string matching algorithm very similar to Commentz-Walter. </p>