Aho-Corasick Algorithm

A multi-pattern string matcher that builds an automaton over a trie with failure links to scan text in linear time.

Matching many patterns at once

Aho-Corasick finds all occurrences of a set of patterns in a text in O(n + m + z) time, where n is the text length, m the total pattern length, and z the number of matches. It builds a trie of the patterns, then adds failure links so that a single left-to-right scan of the text never backtracks.

Failure links

Kronos motion — parameter scan

A failure link from a node points to the longest proper suffix of that node's string that is also a prefix of some pattern (a node in the trie). When the automaton cannot extend a match on the next character, it follows failure links until it can, exactly like the fallback in KMP generalized to many patterns. Output links collect all patterns ending at the current state.

Building failure links (BFS)

python

from collections import deque

def build_fail(root):
    q = deque()
    for c, nxt in root.kids.items():
        nxt.fail = root; q.append(nxt)
    while q:
        u = q.popleft()
        for c, v in u.kids.items():
            f = u.fail
            while f and c not in f.kids:
                f = f.fail
            v.fail = f.kids[c] if f and c in f.kids else root
            v.output = v.fail.output + v.patterns
            q.append(v)

Uses

Virus and intrusion signature scanning across a fixed dictionary.
Keyword filtering, content moderation, and log analysis.
Bioinformatics motif search over DNA and protein sequences.
Dictionary matching as a preprocessing step for other text algorithms.

Relationship to other structures

The trie with failure links is a deterministic finite automaton; converting failure transitions into a full goto table gives constant-time transitions per character. This mirrors how a suffix automaton recognizes substrings, but Aho-Corasick recognizes a chosen dictionary.