What is the Aho-Corasick Algorithm?
Learn how the Aho-Corasick algorithm finds multiple patterns in one pass using a trie and failure links, and how to explain it in interviews.
Expected Interview Answer
Aho-Corasick is a multi-pattern string-matching algorithm that builds a trie of all patterns augmented with failure links, letting it search text for every occurrence of every pattern simultaneously in O(n + m + z) time, where n is text length, m is total pattern length, and z is the number of matches found.
The algorithm first inserts every pattern into a trie, then runs a BFS over the trie to compute a failure link for each node — pointing to the longest proper suffix of that node's path which is also a prefix of some pattern, similar in spirit to KMP's failure function but generalized across many patterns at once. While scanning the text once, whenever a character causes no matching child, the automaton follows failure links instead of restarting, guaranteeing every character of the text is processed in amortized constant time. Output links additionally chain together nodes representing patterns that are suffixes of one another, so a single position can report multiple matches without extra scanning. This makes Aho-Corasick the standard tool for dictionary-style search: antivirus signature scanning, intrusion detection, and searching for thousands of keywords in one pass over a document.
- Searches for many patterns in a single linear pass
- O(n + m + z) time regardless of number of patterns
- Failure links avoid re-scanning text on mismatches
- Output links report all matches ending at a position
AI Mentor Explanation
Aho-Corasick is like a scouting system that watches a bowler's entire spell while simultaneously checking for dozens of known bowling-action signatures at once, instead of re-watching the footage separately for each signature. It builds a single tree of all known actions first, then adds shortcut links so that if the current action stops matching one signature, it instantly knows the longest partial match it can fall back to among all the other signatures, without rewinding the tape. As the spell is watched just once, multiple signatures can be confirmed at the same delivery through linked output markers, like noticing both a slower-ball grip and a wrist-position tell in the same frame. This is why a single pass over the footage can flag every known pattern instead of running one pass per signature.
Step-by-Step Explanation
Step 1
Build the trie of all patterns
Insert every pattern into a shared trie, marking nodes that complete a pattern.
Step 2
Compute failure links via BFS
For each node, link to the longest proper suffix of its path that is also a prefix of some pattern.
Step 3
Chain output links
Link nodes whose path is itself a suffix of another matching pattern, so one position reports multiple matches.
Step 4
Scan the text once
Follow trie edges when possible, else follow failure links, reporting matches via output links at each position.
What Interviewer Expects
- Explain the trie-of-patterns plus failure-link construction
- State the O(n + m + z) time complexity and what each term means
- Contrast with running KMP once per pattern (O(n * k) for k patterns)
- Give a real use case: antivirus signatures, intrusion detection, keyword filtering
Common Mistakes
- Confusing Aho-Corasick failure links with a single KMP failure function
- Forgetting output links, which miss matches that are suffixes of other patterns
- Claiming it only finds one match per position instead of all overlapping ones
- Not recognizing it beats running KMP separately for each pattern
Best Answer (HR Friendly)
“Aho-Corasick lets you search for thousands of keywords in a document in a single pass, instead of scanning the document once per keyword. It builds a combined search tree from all the keywords with smart fallback links, so I would reach for it whenever I need fast multi-pattern search, like scanning for banned words or malware signatures.”
Code Example
from collections import deque, defaultdict
class AhoCorasick:
def __init__(self, patterns):
self.goto = [defaultdict(int)]
self.fail = [0]
self.output = [[]]
for pattern in patterns:
self._insert(pattern)
self._build_failure_links()
def _insert(self, pattern):
node = 0
for ch in pattern:
if ch not in self.goto[node]:
self.goto.append(defaultdict(int))
self.fail.append(0)
self.output.append([])
self.goto[node][ch] = len(self.goto) - 1
node = self.goto[node][ch]
self.output[node].append(pattern)
def _build_failure_links(self):
queue = deque()
for ch, nxt in self.goto[0].items():
self.fail[nxt] = 0
queue.append(nxt)
while queue:
node = queue.popleft()
for ch, nxt in list(self.goto[node].items()):
queue.append(nxt)
fallback = self.fail[node]
while fallback and ch not in self.goto[fallback]:
fallback = self.fail[fallback]
self.fail[nxt] = self.goto[fallback].get(ch, 0) if self.goto[fallback].get(ch, 0) != nxt else 0
self.output[nxt] += self.output[self.fail[nxt]]
def search(self, text):
node = 0
matches = []
for i, ch in enumerate(text):
while node and ch not in self.goto[node]:
node = self.fail[node]
node = self.goto[node].get(ch, 0)
for word in self.output[node]:
matches.append((i - len(word) + 1, word))
return matchesFollow-up Questions
- How does Aho-Corasick's failure link generalize the KMP failure function?
- Why do you need output links in addition to failure links?
- How would you use Aho-Corasick to build a real-time content filter?
- How does the total memory usage scale with the number and length of patterns?
MCQ Practice
1. What is the time complexity of Aho-Corasick search over text of length n with total pattern length m and z matches?
Aho-Corasick processes the text once, with failure links avoiding backtracking, giving O(n + m + z) total.
2. What is the primary advantage of Aho-Corasick over running KMP once per pattern?
Aho-Corasick merges all patterns into one automaton so the text is scanned only once, instead of once per pattern.
3. What do output links in Aho-Corasick handle?
Output links chain nodes so that when a longer pattern matches, any shorter pattern that is a suffix of it is also reported at that position.
Flash Cards
What structure does Aho-Corasick build from the patterns? — A trie of all patterns, augmented with failure links computed via BFS.
What is Aho-Corasick’s time complexity? — O(n + m + z), where n is text length, m is total pattern length, z is number of matches.
What do failure links let the automaton do? — Continue matching after a mismatch without restarting or re-scanning the text.
Name a real-world use case for Aho-Corasick. — Antivirus signature scanning, intrusion detection, or multi-keyword content filtering.