CoreSource checked

Aho-Corasick

Finds many patterns in one text scan using an automaton.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pattern Matching
Difficulty: Advanced
Family: Automaton Matching
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 5
Code example: Not ready
Visualization: Ready

Overview

Aho-Corasick builds a trie of patterns with failure links so matching can continue efficiently after mismatches.

Core Concepts

pattern comparisonstring sequencefinite-state automatonprefix pathautomaton matchingsequence scanpattern statematch verification

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n + m)

Average

O(n + m + z)

Worst

O(n + m + z)

Space

O(m)

When to Use

Use Aho-Corasick when you need to build a pattern trie.
Use it for keyword filtering with inputs like text.
Use it when exact, fuzzy, or structured patterns must be found in sequences.
Use it when the Automaton Matching tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when preprocessing cost is larger than a one-off simple scan.
Avoid it when the required output is not pattern match positions.

What It Does

Builds a pattern trie
Uses failure links to scan text once

Use Cases

Keyword filtering
Multiple pattern search
Intrusion detection

Inputs

Text
Set of patterns

Outputs

Pattern match positions

Key Formulas (1)

Failure transition

while state has no edge for char, state = failure_[state]

while state has no edge for char, state = failure[state]

Falls back through suffix links until the next character can be consumed.

Pseudocode

1.Build a trie from all patterns
2.Add failure links between trie nodes
3.Scan text character by character
4.Follow failure links after mismatches
5.Report patterns attached to reached nodes

Canonical Example

Input: text = 'abracadabra', pattern = 'abra'
Output: matches at positions [0, 7]
Explanation: Aho-Corasick: The algorithm scans the sequence and reports where the pattern appears.

Implementation Notes

Keep the input contract explicit: Text; Set of patterns.
Use this step as the implementation spine: Build a trie from all patterns.
Then preserve the next state change: Add failure links between trie nodes.
Decide whether indexes mean bytes, code units, characters, or tokens.
Test overlapping matches, empty patterns, repeated characters, and no-match inputs.

Common Pitfalls

Aho-Corasick is strong when many patterns must be searched at once.
Indexing by bytes instead of characters can break text with multibyte characters.
Reporting a match before verifying collisions, boundaries, or full-pattern alignment.
Returning pattern match positions without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Sequence Window & Automaton Alignment

Show text moving through a trie with failure links.

Input:ABABABCABAB

Window:ABAB

Step 1 of 5: Build a trie from all patterns

pattern-automaton

Notes

Aho-Corasick operates in O(n + m + z) time and O(m) space within the Automaton Matching family. Key governing relation: while state has no edge for char, state = failure[state]. Often compared with Trie and Knuth-Morris-Pratt.