Commentz-Walter algorithm

The Commentz-Walter algorithm is a string searching algorithm that looks for several patterns in a text at once. It was invented by Beate Commentz-Walter, whose paper was first published through Saarland University in 1979. It combines the multi-pattern automaton idea of the Aho-Corasick algorithm with the backward scanning and large shifts of the Boyer-Moore algorithm. In a precomputation phase a pattern tree is built from the reversed patterns, and in the matching phase the text is scanned backwards, with a shift table telling how far to move after a mismatch. For a text of length n and a longest pattern of length m the worst-case running time is O(mn), which it inherits from Boyer-Moore, although the average case is often much better and with few matches both this method and Aho-Corasick approach linear time. Published analyses suggest it can beat Aho-Corasick when the patterns are long, but the source notes that there is no general agreement on that. GNU grep once used a very similar algorithm.