Aho-Corasick Algorithm
When to Use
| Approach | Time | Use when | |----------|------|----------| | Brute force | O(n × m) | one pattern, tiny text | | KMP × k | O(n × k + m) | few patterns | | Aho-Corasick | O(n + m + z) | many patterns, single pass |
n = text length, m = total pattern length, k = pattern count, z = match count.
Key Concepts
- Trie: insert all patterns; each node = prefix
- Failure link
fail[v]: longest proper suffix of the string atvthat is al
[Description truncada. Veja o README completo no GitHub.]