Wu-Manber Algorithm

Purpose: Multi-pattern string matching that is sublinear in practice — it skips characters like Boyer-Moore does, rather than reading every character like Aho-Corasick. This is the algorithm behind agrep and, historically, grep -F with many patterns.

The Idea

Let $m$ be the length of the shortest pattern. Choose a small block size $B$ (typically 2 or 3 characters).

Three tables, all built over blocks rather than single characters:

1. SHIFT — for each $B$-character block, how far the search window can safely jump. If a block never occurs in any pattern, jump the full $m-B+1$. Otherwise jump $m-(\text{rightmost position of that block})-1$.
2. HASH — for blocks that end some pattern, a list of the pattern ids ending with that block.
3. PREFIX — the first two characters of each pattern, used to reject candidates cheaply before a full comparison.

Algorithm

1. Align the window so its right end is at text position $i$, starting at $i=m-1$.
2. Hash the last $B$ characters of the window, look up SHIFT.
3. If SHIFT > 0, advance $i$ by that amount and repeat — no character in between is examined.
4. If SHIFT == 0, this block ends at least one pattern. Check the PREFIX filter, then verify each candidate in HASH by direct comparison. Advance $i$ by 1.

Complexity

• Preprocessing: $O(\sum |P_i|)$
• Average: sublinear — roughly $O(nB/m)$ text accesses when patterns are long relative to $B$ and the alphabet is not tiny
• Worst case: $O(n\cdot \sum |P_i|)$ — degrades badly when many patterns share suffixes
• Space: $O({\sigma }^B)$ for the shift table (which is why $B$ stays at 2-3)

Wu-Manber vs Aho-Corasick

	Wu-Manber	Aho-Corasick
Guarantee	none (worst case bad)	$O(n+\sum \Vert P_i\Vert +\text{occ})$ always
Practice	faster when patterns are long	faster when patterns are short
Memory	$O({\sigma }^B)$ tables	$O(\sigma \sum \Vert P_i\Vert )$ automaton
Sensitive to	the shortest pattern length	nothing much

The shortest pattern rules everything

Wu-Manber’s skip distance is capped by the shortest pattern. One two-character pattern in a set of thousand-character patterns destroys the entire advantage. Real implementations special-case short patterns into a separate Aho-Corasick pass.

Paradigm

Bad-character skipping generalised to blocks, plus hashing to handle many patterns at once. The block hashing is what turns Boyer-Moore’s single-pattern skip into a multi-pattern one.

Variants / Use Cases

• agrep — Wu and Manber wrote both the algorithm and the tool
• Intrusion detection (Snort) and antivirus scanners — thousands of signatures against a fast stream
• Commentz-Walter — the earlier Boyer-Moore + Aho-Corasick hybrid that Wu-Manber simplifies and beats
• Aho-Corasick — what you write in a contest; guaranteed linear, much shorter code
• Boyer-Moore — the single-pattern ancestor