How to Learn Aho–Corasick: Tries, Failure Links, Output Links and One-Pass Multi-Pattern String Matching

Wait, What?

Searching for one word at a time can be the wrong problem when the real task is to search for thousands of words at once.

Aho–Corasick is a multi-pattern string-matching algorithm. Instead of scanning the same text separately for every keyword, it preprocesses the whole dictionary into a finite-state machine and then streams through the text once, reporting every matching pattern encountered along the way.

That makes it a beautiful algorithm for learning because it connects several ideas that beginners often meet separately: tries, breadth-first search, suffixes, automata, preprocessing, streaming and output-sensitive complexity. At professional level, the same ideas appear in search systems, security tooling, text classification pipelines, bioinformatics and any application that must recognise many fixed patterns in a large stream.

Quick Answer

Learn Aho–Corasick in this order: single-pattern search → many-pattern search → trie → suffix intuition → failure links → output links → BFS construction → streaming search → complexity → Unicode and memory engineering → dynamic dictionaries → professional validation. Do not begin with the full automaton. First understand why repeated independent searches waste work.

1. Begin with the problem, not the name

Suppose you must scan the text:

ushers

for the patterns:

he
she
his
hers

You could run four separate searches. That works, but every search rereads much of the same text. Aho–Corasick asks a different question: can the patterns share their common prefixes and can the search reuse information when one prefix fails?

The answer is yes. The trie shares prefixes; failure links reuse suffix information.

2. The trie is the visible skeleton

Insert every pattern into a trie. If two patterns begin with the same characters, they share the same initial path.

For example, he, hers and his all begin at the root with h. The trie stores that shared structure once.

A terminal marker at a trie node records that one or more patterns end there. At this stage the structure can recognise patterns if the text happens to stay on trie edges. It still does not know what to do efficiently when the next character does not match.

3. The beginner breakthrough: failure does not mean restart

Imagine that the machine has matched a prefix, but the next text character has no outgoing trie edge. A naive approach jumps all the way back to the root and may repeat work.

Aho–Corasick instead asks: what is the longest proper suffix of what I have matched that is also a trie prefix?

The failure link points to the state representing that suffix. This is conceptually related to the fallback idea in KMP, but now the state space is a trie of many patterns rather than the prefixes of one pattern.

4. A concrete suffix example

Suppose the machine has reached the state for she. The suffix he is also a pattern and also a trie path. Therefore the state for she can fail to the state for he.

This matters because reading she should report both she and he. The machine should not forget the shorter suffix match merely because the longer pattern finished first.

5. Output links are not optional decoration

Each state needs to know which patterns should be reported when that state is reached. That can include a pattern ending at the state itself and patterns ending at states reached through suffix/failure relationships.

A common implementation stores an output list at each state and propagates inherited matches during construction. Another stores a separate output-link chain. The representation can vary; the correctness requirement cannot: all patterns ending at the current text position must be recoverable.

6. Build failure links breadth-first

Failure links are naturally constructed with BFS because a node’s failure target is found from shallower states whose own failure links have already been computed.

Conceptually:

queue = children(root)
for each child of root:
    fail[child] = root

while queue not empty:
    v = pop_front(queue)

    for each character c and child u of v:
        f = fail[v]

        while f is not root and no transition(f, c):
            f = fail[f]

        if transition(f, c) exists and transition(f, c) != u:
            fail[u] = transition(f, c)
        else:
            fail[u] = root

        output[u] += output[fail[u]]
        push_back(queue, u)

Production implementations often fill missing transitions so that search can use direct table lookups instead of an explicit while-loop.

7. Searching becomes a state-machine walk

Once construction is complete, scan the text left to right. For each character, follow the next transition if possible. If not, follow failure links until a valid transition is found or the root is reached.

After entering the new state, report every pattern in that state’s output set.

state = root

for i, c in text:
    while state != root and no transition(state, c):
        state = fail[state]

    if transition(state, c):
        state = transition(state, c)
    else:
        state = root

    for pattern in output[state]:
        report(pattern, i)

The reported end position lets you reconstruct the start position from the pattern length.

8. Why the algorithm is powerful

The original Aho–Corasick paper describes construction time proportional to the total length of the keywords and a single pass over the text with state transitions independent of the number of keywords. In common complexity notation, practical implementations are often summarised as roughly O(total pattern length + text length + number of reported matches), with representation-dependent factors for transitions and alphabet handling.

The important idea is not just the formula. The dictionary is preprocessed once, and the text is not rescanned independently for each pattern.

9. The match count matters

No algorithm can report a million matches in zero time. If the text and dictionary create many overlapping matches, output processing can dominate the search.

That is why the + z term—where z is the number of reported occurrences—is important when discussing complexity honestly.

10. Dense and sparse transition tables

If the alphabet is tiny, each state can store a dense array of transitions. This gives fast predictable lookup but can waste memory.

For a large alphabet, sparse maps or compressed representations may be more appropriate. The trade-off becomes:

• memory per state;
• transition lookup cost;
• cache locality;
• construction cost;
• alphabet normalisation.

Professional performance depends as much on representation as on the high-level algorithm.

11. Unicode is a modelling decision

Aho–Corasick operates on symbols. The difficult part is deciding what a symbol means in your application.

Are you matching bytes, Unicode code points, grapheme clusters, case-folded text or normalised text? The same visible word can have different underlying Unicode representations. If the pattern dictionary and text are normalised differently, correct automaton logic can still produce incorrect product behaviour.

Define normalisation before building the trie.

12. Streaming is a natural fit

The current automaton state is enough to continue searching when the next chunk arrives. That makes Aho–Corasick suitable for streamed text, logs and network-like data, provided the symbol encoding and chunk boundaries are handled correctly.

You do not need to restart the search at every chunk. Keep the automaton state and continue.

13. Static dictionaries are the easy case

Aho–Corasick is most straightforward when the pattern set is fixed for many searches. If patterns are inserted or removed constantly, rebuilding the automaton may become expensive.

Professional systems may batch updates, maintain multiple automatons, use dynamic variants, or choose another indexing strategy. Do not assume that a brilliant static algorithm automatically solves a dynamic workload.

14. Failure links are not backtracking through the text

The machine moves through states representing useful suffixes. The text index continues forward. This distinction is important: fallback changes the pattern state, not the already-consumed text.

Ask learners to trace the state sequence on paper. If they repeatedly move the text pointer backwards, they have misunderstood the algorithm.

15. A strong learning trace

Use a tiny dictionary such as:

he, she, his, hers

and trace the text:

ushers

Record four columns:

character | trie/state entered | failure used? | outputs

This makes the invisible automaton behaviour visible and exposes the exact moment when she also yields he.

16. How to teach Aho–Corasick from beginner to professional

A productive progression begins with reading and tracing before implementation.

• Predict: given a trie and one text character, predict the next state.
• Run: use a trusted implementation on a tiny dictionary.
• Investigate: trace failure links and inherited outputs.
• Modify: add one pattern that is a suffix of another and predict what changes.
• Make: implement construction and search, then compare against a naive oracle.

This follows current programming-education evidence favouring code comprehension, worked examples and faded scaffolding before unsupported construction.

17. Test against a deliberately slow oracle

For small inputs, write the simplest correct baseline: for every pattern, search every possible text position. It may be slow, but it is transparent.

Generate random small pattern sets and random texts. Compare the complete multiset of matches from the naive oracle and your Aho–Corasick implementation. This is far stronger than checking two hand-picked examples.

18. Edge cases worth forcing

• empty text;
• one pattern;
• duplicate patterns;
• one pattern that is a suffix of another;
• patterns sharing long prefixes;
• overlapping occurrences;
• all patterns consisting of the same repeated symbol;
• characters absent from every pattern;
• very large dictionaries;
• Unicode normalisation differences.

19. Professional engineering questions

Before deploying, answer these explicitly:

• Is the dictionary static or dynamic?
• What is the alphabet?
• How is text normalised?
• Do we need all matches or only existence/counts?
• Can output volume become enormous?
• Should transition storage be dense, sparse or compressed?
• Can the automaton be shared safely across threads?
• How will updates be rolled out and versioned?

20. Common failure states

• Building only a trie and calling it Aho–Corasick.
• Computing failure links but forgetting inherited outputs.
• Restarting the text scan after a mismatch.
• Assuming duplicate patterns have no semantic effect.
• Ignoring Unicode normalisation.
• Benchmarking only search time while excluding automaton construction when rebuilds are frequent.
• Comparing implementations with different output requirements.
• Reporting complexity without accounting for the number of matches emitted.

21. When another algorithm is simpler

If you have one pattern, KMP, Boyer–Moore-family methods or a standard library search may be simpler. If the text is fixed and many arbitrary queries arrive later, suffix arrays, suffix trees or full-text indexes may fit better. If patterns contain wildcards or regular expressions, a regex engine or specialised automaton may be the real problem.

The professional skill is not memorising Aho–Corasick. It is recognising the workload shape it owns.

22. Practice ladder

• Beginner: build and draw a trie for five words.
• Foundation: identify the longest useful suffix for each trie node.
• Intermediate: compute failure links with BFS and trace all matches.
• Advanced: implement sparse and dense transition strategies and benchmark them.
• Professional: design a streaming matcher with Unicode policy, versioned dictionaries, property-based validation and workload-aware memory benchmarks.

23. Ownership boundary

This article owns the Aho–Corasick multi-pattern matching algorithm: trie construction, failure transitions, output propagation, streaming search and production implementation trade-offs. It does not replace general string algorithms, regex engines, full-text indexing, language parsing, security policy, learner measurement or student-interface design.

Sources and further reading

• Alfred V. Aho and Margaret J. Corasick, “Efficient String Matching: An Aid to Bibliographic Search,” Communications of the ACM, 18(6), 1975. DOI: 10.1145/360825.360855.
• NIST Dictionary of Algorithms and Data Structures, “Aho–Corasick”: NIST DADS.
• ACM/IEEE-CS/AAAI CS2023, Algorithmic Foundations: CS2023 Algorithmic Foundations.
• Sue Sentance, Jane Waite and Maria Kallia, research on PRIMM and code-first comprehension in programming education: SIGCSE 2019.
• Yoonhee Shin et al., worked examples and metacognitive scaffolding for programming problem solving, 2023: Journal of Educational Computing Research.

Professional rule: you understand Aho–Corasick when you can explain why a failed prefix becomes a useful suffix, prove that every required match is still reported, and choose a representation that fits the real alphabet, update pattern and output volume of your workload.