Commentz-Walter algorithm とは

コンピュータサイエンスでは、Commentz-Walterアルゴリズムは、Beate Commentz-Walterによって考案された文字列検索アルゴリズムです。 Aho-Corasick文字列マッチングアルゴリズムと同様に、複数のパターンを一度に検索できます。 Aho-CorasickのアイデアとBoyer-Mooreの文字列検索アルゴリズムの高速マッチングを組み合わせたものです。長さnと最大パターン長mのテキストの場合、その最悪ケースの実行時間はO(mn)ですが、平均的なケースはしばしばはるかに優れています。
GNU grepは、Commentz-Walterによく似た文字列マッチングアルゴリズムを実装しています。