Back to 20 Concepts
advanced-strings • Expert
Aho-Corasick Multi-Pattern Dictionary Matching
Aho-Corasick constructs a Finite State Machine combining a Trie with KMP-style failure transitions, finding all occurrences of K dictionary keywords in a text in O(N + M + Z) time.
Intuitive Mental Model
The Security Checkpoint Scanner: As luggage moves along the conveyor belt (text stream), the scanner matches against 1,000 banned items simultaneously in a single forward pass without pausing.
C / TypeScript ImplementationHardware & Algorithmic Standard
// Aho-Corasick State Machine:
// 1. Build Trie over Dictionary keywords { "he", "she", "his", "hers" }
// 2. Compute BFS Failure Links (Fallback on mismatch)
// 3. Scan Text in O(N) single pass: All keyword matches emitted simultaneously!Key Architectural Takeaways
- •Single Pass Multi-Pattern: Searches for 10,000 patterns in text simultaneously in O(TextLength + TotalMatches).
- •Antivirus & Intrusion Detection: Used in Snort, ClamAV, and packet inspection firewalls.
Common Coding Mistake
Running KMP K separate times for K patterns (O(K * N)), multiplying execution time by 1,000x.
Optimal Solution
Use Aho-Corasick for simultaneous multi-keyword dictionary matching.