Commentz-Walter Algorithm

Purpose: Multi-pattern matching that combines Aho-Corasick’s trie with Boyer-Moore’s right-to-left skipping. Historically the first practical sublinear multi-pattern algorithm (1979).

The Idea

1. Build a trie of the reversed patterns. Matching then proceeds right to left within the window, just as Boyer-Moore does.
2. Compute two shift functions, shift1 and shift2, that generalise Boyer-Moore’s good-suffix rule to a set of patterns, plus a bad-character table.
3. Slide a window of width $m_{\min }$ (the shortest pattern length). At each position, walk the reversed trie backwards from the window’s right end. Report any pattern that completes. Then shift by the maximum safe amount permitted by the tables.

Complexity

• Preprocessing: $O(\sum |P_i|)$
• Average: sublinear, similar in spirit to Boyer-Moore
• Worst case: $O(n\cdot m_{\max })$ — worse than Aho-Corasick’s guaranteed linear
• Space: $O(\sum |P_i|\cdot \sigma )$ for the trie plus $O(\sigma )$ for the shift tables

Why it has been superseded

The shift computations are intricate and the worst case is unbounded. Wu-Manber achieves the same sublinear behaviour with dramatically simpler machinery (block hashing instead of two generalised good-suffix functions) and is faster in practice. Meanwhile Aho-Corasick offers a hard linear guarantee with about 30 lines of code.

So Commentz-Walter’s place today is historical: it is the bridge between the two great single-pattern paradigms — automaton-based (KMP, Aho-Corasick) and skip-based (Boyer-Moore) — applied to sets.

The three approaches to multi-pattern matching

Approach	Representative	Guarantee	When to use
Automaton, left to right	Aho-Corasick	$O(n+\sum \Vert P\Vert +\text{occ})$	contests, always
Trie + skipping, right to left	Commentz-Walter	none	historical
Block hashing + skipping	Wu-Manber	none	long patterns, huge texts
Bit-parallel	Bitap variants	$O(n\sum \Vert P\Vert /w)$	few short patterns
Hashing	Rabin-Karp multi	$O(n)$ expected	equal-length patterns

Variants / Use Cases

• fgrep in some historical Unix implementations — the original deployment
• Wu-Manber — the direct successor; prefer it if you need skipping
• Aho-Corasick — the topic page and the practical choice
• Strings — the branch overview