Aho-Corasick
Searches for many patterns at once in a single pass over the text, using a trie of all patterns augmented with failure links (like KMP's failure function, generalised from one pattern to a whole trie).
- Category
- Strings
- Time complexity
- O(n + m + z)
- Space complexity
- O(m·Σ)
Pseudocode
build a trie of all patterns BFS to compute failure links (like KMP, per trie node) scan text once, following goto/fail transitions each node visited reports every pattern ending there
Reference implementation
# build trie + fail links, then scan once:
node = root
for ch in text:
while node is not root and ch not in node.next:
node = node.fail
node = node.next.get(ch, root)
for pat in node.out: report_match(pat)