Pebellslearn by building
0%
RoadmapsMatrixCoursesSandboxSign in
String Algorithms  ›  Lesson

Aho-Corasick: Matching Many Patterns at Once

Aho-Corasick 30 minA trie of patterns with failure links, so one text pass finds every pattern
You're building a piece ofQuarry — the text index
This piece — kmp_search(): Finds every occurrence in one forward pass, never re-reading the text.
Scenario Quarry's text index needs to flag every one of a few thousand tracked phrases inside a new document without rereading the document once per phrase.
Your task
Build find_all_patterns(text, patterns): for every pattern, the list of starting indices where it occurs in text, found in one pass over text using the Aho-Corasick automaton (a trie of the patterns with failure links). Example: find_all_patterns("ushers", ["he", "she", "his", "hers"]) -> {"he": [2], "she": [1], "his": [], "hers": [2]}.

Aho-Corasick: Matching Many Patterns at Once

In short: KMP finds one pattern in one text pass. Aho-Corasick finds every pattern in a whole dictionary in one text pass. Build a trie (section 4's structure) of all the patterns, then give every node a failure link — "if matching breaks here, where in the trie should I carry on from?" — the same idea as KMP's border, generalised from one string to a whole tree of them. The text pointer still never moves backwards; only the trie pointer jumps.

A trie of the words he, she, his and hers, with a dashed failure-link arrow from the deep node reached by 's','h' pointing back up to the node reached by 'h' alone

Scanning a document for every banned word at once

A moderation filter checks a post against a list of a thousand banned phrases. Calling .find() once per phrase means reading the post a thousand times — O(n · k) for k phrases. A trie merges the phrases that share a prefix, so the text is only ever read once, no matter how many phrases there are.

python

This gives the right answer, but it scans "ushers" four separate times. Aho-Corasick reads it once and finds all four matches (or, here, the three that actually occur) as it goes.

Building the trie, then the failure links

The trie part is exactly lesson 4's: insert every pattern character by character, sharing prefixes. Aho-Corasick adds a second pass over the trie, breadth-first, giving every node a failure link — the node you'd be at if you'd started matching from the next possible alignment instead. It is built the same way KMP's failure function is: a node's failure link follows its parent's failure link, extended by the same character, climbing until a match is found or the root is reached.

python

output[v] |= output[fail[v]] is the detail that's easy to miss: if "he" ends at a node, and a longer pattern's failure link lands there, "he" has to be reported too — a match doesn't stop being a match just because a longer pattern also matched at the same spot.

Walking the text once

The scan looks exactly like KMP's, except "no match, follow the failure link" now jumps between trie nodes instead of positions in one pattern, and every node's output set can report more than one pattern at once.

watch it move · tree

Scanning "ushers" against he, she, his, hers in one pass. A ● node ends a pattern. Watch the pointer jump on the 'r' mismatch instead of restarting.

Text pointer at 'u' (index 0). The root has no u edge, so the trie pointer just stays put — no failure link needed when there was nothing to fail from. Binary tree, 10 nodes, height 5. At node root.

1 / 8

Quick practice

What does this print?
def contains_prefix(patterns, s):
    children = [{}]
    for p in patterns:
        node = 0
        for ch in p:
            if ch not in children[node]:
                children.append({})
                children[node][ch] = len(children) - 1
            node = children[node][ch]
        # (output tracking omitted — not needed for this check)
    node = 0
    for ch in s:
        if ch not in children[node]:
            return False
        node = children[node][ch]
    return True

print(contains_prefix(["he", "she"], "sh"), contains_prefix(["he", "she"], "hi"))
broken — fix it

This should count 3 matches (she, he, hers all occur once) but under-counts because shorter patterns reachable only by a failure link go unreported. Restore the missing output merge.

What it costs

step cost
building the trie of k patterns, total length M O(M)
building the failure links (one BFS) O(M)
scanning text of length n O(n) — same amortised argument as KMP: the trie pointer's depth rises by at most 1 per character and each failure-link step only ever lowers it
total for k patterns, total length M, over text of length n O(M + n), not O(n · k)

🎯 Your turn

Build find_all_patterns(text, patterns): for every pattern, the list of starting indices where it occurs in text, found in one pass over text using the Aho-Corasick automaton.

  • find_all_patterns("ushers", ["he", "she", "his", "hers"]) → {"he": [2], "she": [1], "his": [], "hers": [2]}
  • find_all_patterns("abcabc", ["abc", "bc", "c"]) → {"abc": [0, 3], "bc": [1, 4], "c": [2, 5]}

Hint: build the trie and failure links from the code above, then walk text once: on a mismatch follow fail[node]; after moving to the next node, every pattern index in output[node] matched ending at the current text position — record i - len(pattern) + 1.

Press ▶ Run, then ✓ Check.

Practice — level up

0/5 solved

Solve each in its own editor — Run to try, Check to grade. Stuck? Reveal a Hint, or the full Solution + walkthrough.

Warm-upHow big is the trie?

Write trie_size(patterns): the number of nodes in the trie of patterns (including the root), sharing prefixes the way a trie does.

tries
DrillIs it a prefix of anything?

Write contains_prefix(patterns, s): whether s is a prefix of at least one string in patterns (including s being a whole pattern, or the empty string, which is a prefix of everything).

tries
BuildThe failure links themselves

Write build_fail_links(patterns): build the trie of patterns, then return the fail list (the failure link for every node, in node-insertion order; the root's is 0).

string-matchingtries
BossCount every match in one pass

Write count_all_matches(text, patterns): the TOTAL number of pattern occurrences in text (summed across all patterns, counting overlaps), found in one pass with the full automaton (trie + failure links + inherited output).

string-matchingtries
CapstoneJust the first occurrence of each

Write first_match_each(text, patterns): for every pattern, its FIRST starting index in text, or -1 if it never occurs — found in one pass with the automaton, stopping early per pattern once its first hit is recorded.

string-matchingtries
find_all_patterns.py
Call the function you wrote — just like your app's frontend would. Edit the inputs and hit Call.
find_all_patterns(text, patterns) → dictEvery starting index where each pattern occurs in text.
try:
returned
Press Run to execute your code.
Press Check to run the tests for this lesson.