Coding interview: Implement Aho–Corasick multi-pattern matching

Prompt and context

This is a multi-pattern matching problem for log filtering, sensitive-word detection, or editor highlighting. Let total keyword length be M and text length be N; report each match start and keyword ID. The dictionary is fixed during preprocessing, the text may be long, and the interviewer expects preprocessing, scan complexity, and overlap handling.

What the interviewer evaluates

The interviewer wants you to extend trie prefix sharing into a finite-state machine. A strong answer builds failure links, inherits outputs along failure links, and explains why each character causes bounded state transitions. A weak answer says “use a trie” but cannot handle suffix overlap or mismatch fallback.

Clarifications to ask first

• Is matching case-sensitive, Unicode-normalized, or byte-based? The character definition changes the trie and position unit.
• Must overlapping matches and multiple keywords ending at one position be returned? This determines whether the output chain is complete.
• Does the dictionary change frequently? A static dictionary fits one automaton; a dynamic dictionary may need versioned rebuilds.
• Are positions counted in characters, bytes, or UTF-16 code units? Match the caller’s contract.
• Does text arrive in chunks? Cross-chunk scanning must preserve state instead of resetting each chunk.

30-second answer framework

“I would insert every keyword into a trie, then use BFS to build a failure link for each node: the longest usable suffix after a mismatch. Each node combines its own terminal outputs with outputs from its failure target. During scanning, follow transitions or failure links and emit the current node’s outputs. Preprocessing is linear in total keyword length plus edge representation; scanning is O(N + matches), and chunked input only needs the current automaton state.”

Step-by-step deep answer

1. Build the trie. Each node stores child edges, a failure link, and keyword IDs. A terminal node appends an ID; it must not keep only one.
2. Initialize failures. Direct children of the root fail to the root. Process the remaining nodes by depth with a queue.
3. Compute fallback transitions. For an edge from a node, follow the parent’s failure links until the same character edge is found; otherwise return to root. Scanning then never re-compares earlier text characters.
4. Aggregate outputs. Copy outputs from the failure target or store an output link to avoid copying lists; an output link is traversed when reporting matches.
5. Scan text. Try a child edge for each character. On mismatch, follow failure links until an edge or root is reached. Emit every output at the new node; start is current index minus keyword length plus one.
6. Handle boundaries. Overlapping keywords are emitted naturally. Chunked input carries state between chunks. If matches are huge, use a callback, cap, or pagination instead of retaining all O(matches) results.

Use a hash map for general alphabets and an array for a small fixed alphabet when memory permits. For a changing dictionary, build a new version in the background and atomically switch readers so scans never observe a partial automaton.

Model answer

“I would insert all keywords and record each terminal ID, then BFS-build failure links. Root children fail to root. For other edges, follow the parent’s failure chain to find the same transition or fall back to root. Outputs include the node’s own terminal IDs and failure outputs, so both he and she are emitted while scanning she. Each text character follows a child or failure transition, giving O(N + Z) scan time where Z is the number of matches; preprocessing is O(M) plus edge storage. Chunked text preserves state, and dictionary updates build a new version before switching.”

Common mistakes

• Mistake: Move both the pointer and text backward on mismatch → Why it fails: It degenerates into rescanning for every keyword → Fix: Failure links keep the text index monotonic.
• Mistake: Keep one output per node → Why it fails: Suffix keywords and shared endpoints disappear → Fix: Merge failure outputs or maintain output links.
• Mistake: Claim scanning is always O(N) → Why it fails: Reporting matches itself can cost O(Z) → Fix: State O(N + Z) and stream output.
• Mistake: Reset to root at every chunk → Why it fails: Keywords spanning chunks cannot match → Fix: Carry the automaton state between chunks.

Follow-up questions and responses

Why not run KMP separately for every keyword?

Separate KMP runs require O(KN) text scans. Aho–Corasick shares trie prefixes and processes the text once, which fits a fixed dictionary and long text.

Why do failure links find every match?

They point to the longest usable suffix. Continuing along the failure chain enumerates every suffix that is also a keyword prefix, so output aggregation finds nested and overlapping matches.

What if child hash maps exhaust memory?

Choose arrays for a small alphabet, compact edge tables, or a double-array trie, and use output links to avoid copying lists. Measure node and edge counts before compressing.

Can the dictionary change frequently?

Version the dictionary, build a new automaton in the background, validate it, and atomically replace the reader pointer. Keep the old version briefly for streams already in progress.