Data Structures And Algorithms Aho

How to Actually Implement Aho-Corasick Without Losing Your Mind

I spent three days debugging a production search system last year that kept returning phantom matches on Russian text input. Turned out my failure function construction was off by one index when processing the null byte at the end of a string. The fix was six lines of code and about four hours of my life I'm never getting back. The Aho-Corasick algorithm is essentially a finite state automaton built from a trie of your keywords, with failure links that let you skip ahead when a match attempt fails instead of restarting from scratch. It finds all occurrences of multiple patterns in a text in linear time relative to the text length plus the total number of matches. That's O(n + m + z) where n is your text length, m is the combined length of all patterns, and z is the number of output matches.

Data Structures And Algorithms Aho

Here's how I actually build one in practice, not the clean textbook version: Start with a trie. Insert each pattern character by character. Each node tracks which patterns end there. Then you build failure links using BFS from the root. The failure link of a node points to the longest proper suffix of the current path that's also a prefix of some pattern. This is the same idea as the KMP failure function but generalized across multiple patterns. For the failure link construction, iterate through the trie in BFS order. For each node at depth d with parent p and edge character c, if p's failure link has a child on c, point the current node there. Otherwise, follow the failure chain up from p's failure link until you find a node with a child on c or hit the root. If you hit the root without finding a match, point to the root.

Here's the part nobody explains well. When you're traversing the text, at each character you follow the failure links to find the longest matching state. But you don't just check the current state for matches. You also have to walk the failure chain from that state to collect all pattern matches that end at the current position. So if your trie has patterns "he", "she", and "his", and you're matching against "ushers", when you reach the 'e' you need to output both "she" and "he" because both end at that position. I wrote a production implementation once that used a compressed output approach to avoid the traversal overhead. Instead of walking failure links at query time, I precomputed which patterns each node could emit by OR-ing together the output of the failure chain during construction. This made the query phase strictly O(n) after the preprocessing step, which matters when you're running this over millions of documents. The preprocessing time is O(m * alphabet) for naive failure link construction or O(m) with optimization. The space complexity is proportional to the number of nodes in the trie, which in the worst case is the sum of all pattern lengths. If you have thousands of long patterns, this can get expensive quickly. I've seen systems where the trie alone consumed over 2GB of RAM for a pattern set of roughly 500,000 strings averaging 200 characters each. Not something you want to spin up on a laptop.

A counter-intuitive thing about this algorithm: it doesn't care about the order of your patterns. The algorithm will find all of them regardless of insertion order. But the failure links are order-dependent in terms of which node gets visited first during BFS, which affects performance slightly. Not enough to matter in most cases, but if you're doing micro-optimization work it's worth knowing. Another thing people miss. Aho-Corasick is fundamentally a string matching algorithm. It is not a general-purpose search tool. If you need fuzzy matching, wildcard support, or proximity constraints, you're using the wrong algorithm. I've seen too many teams slap Aho-Corasick onto a problem it wasn't designed for and then wonder why they're getting false positives or missing legitimate matches due to the rigid prefix structure. For download and reference implementations, the classic C version by Alfred Aho and Margaret Corasick is in the public domain. Their original paper is "Efficient String Matching: An Aid to Bibliographic Search" from 1975. Most modern implementations you'll find on GitHub add features like parallel pattern processing or memory mapping for large pattern sets. The Go implementation by dominiktriebel is decent if you need something production-ready and well-tested.

Common pitfalls include forgetting to handle the case where a node's failure link points to itself (should never happen with correct construction but bugs in recursive implementations can create loops), not properly handling overlapping patterns, and underestimating the memory footprint when your alphabet is large. Unicode inputs without normalization will create massive tries because every variation of a character becomes a separate branch. If you're working with very large pattern sets and your bottleneck is memory rather than speed, consider a two-level approach. Hash-partition your patterns into buckets, build separate Aho-Corasick automata per bucket, then combine results. This trades some complexity for significantly lower peak memory usage and tends to perform better on cache when your pattern set fits in L2 cache per bucket.