Aho-Corasick multiple-pattern matching: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Build a trie, compute failure links breadth first, and report every terminal pattern including suffix matches and duplicates.

Insert every pattern into a shared trie. Compute failure links in breadth-first order and inherit output IDs from each failure target. Scan the text once, following fallback transitions and reporting all matching pattern IDs.

Open the 3D visualization

Aho-Corasick multiple-pattern matching example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Aho-Corasick multiple-pattern matching

Searching one text for a small dictionary of keywords, including overlapping matches.

Choosing an alternative

KMP preprocesses one pattern. Aho-Corasick shares prefixes across a dictionary and keeps suffix matches through failure links.

Worked example: input and state changes

Example input

ushers | he,she,s

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Start with the root.

    State at this checkpoint
    {
      "values": [
        "root"
      ],
      "active": [],
      "kind": "graph",
      "directed": true,
      "chosen": [],
      "visited": [],
      "matches": [],
      "result": 0
    }
  2. Step 4: Insert trie prefix sh.

    State at this checkpoint
    {
      "values": [
        "root",
        "h",
        "he",
        "s",
        "sh"
      ],
      "active": [
        4
      ],
      "kind": "graph",
      "directed": true,
      "chosen": [],
      "visited": [],
      "matches": [],
      "result": 0
    }
  3. Step 8: Compute failure link and inherit suffix outputs.

    State at this checkpoint
    {
      "values": [
        "root",
        "h",
        "he",
        "s",
        "sh",
        "she"
      ],
      "active": [
        5,
        2
      ],
      "kind": "graph",
      "directed": true,
      "chosen": [],
      "visited": [],
      "matches": [],
      "result": 0
    }
  4. Step 11: Read h at 2; report terminal and suffix matches.

    State at this checkpoint
    {
      "values": [
        "root",
        "h",
        "he",
        "s",
        "sh",
        "she"
      ],
      "active": [
        4
      ],
      "kind": "graph",
      "directed": true,
      "chosen": [],
      "visited": [],
      "matches": [
        1,
        2
      ],
      "result": 1
    }
  5. Step 15: Found 4 matches.

    State at this checkpoint
    {
      "values": [
        "root",
        "h",
        "he",
        "s",
        "sh",
        "she"
      ],
      "active": [],
      "kind": "graph",
      "directed": true,
      "chosen": [],
      "visited": [],
      "matches": [
        1,
        2,
        3,
        0,
        3,
        1,
        5,
        2
      ],
      "result": 4
    }

Expected final state

Found 4 matches.

Complexity and input bounds

Family: Strings. Time complexity: O(total pattern length + text length + matches).

Implementation detail: Trie edges show letters and failure edges show fail. The view accepts up to three lowercase patterns with eight letters total. Downloads return inclusive end-index/pattern-ID pairs ordered by end then ID, including overlaps and duplicates.

Space complexity: O(alphabet size times trie nodes) for dense download transitions, plus returned matches and saved frames.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

Text 1..24 lowercase letters | 1..3 patterns, each 1..4 letters, eight pattern letters total.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

A terminal node may report several patterns. Duplicate dictionary entries retain distinct IDs. Inherited outputs are essential when a pattern is a suffix of another.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// Text n 0..24; 0..3 nonempty patterns of 1..4 letters, at most eight pattern letters total. All letters are lowercase ASCII codes 97..122. Patterns flattened into letters with lengths. Output capacity at least 2*n*patterns; writes [inclusive end index, zero-based pattern ID] pairs sorted by end then ID, including overlaps and duplicate patterns. Returns match count. Dense 26-symbol transitions, BFS failure links and inherited outputs. O(total pattern length + n + matches) for fixed alphabet and bounded pattern count; O(26*nodes + matches) storage including output. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(text, n, letters, lengths, patterns, output) {
    let next = Array(256).fill(0); let fail = Array(256).fill(0); let mask = Array(256).fill(0); let queue = Array(256).fill(0); let nodes = 1; let offset = 0; let u = 0; let v = 0; let c = 0; let head = 0; let tail = 0; let state = 0; let count = 0;
    for (let i = 0; i < 256; i++) { next[i] = -1; }
    for (let p = 0; p < patterns; p++) { u = 0; for (let k = 0; k < lengths[p]; k++) { c = letters[offset]-97; offset++; if (next[u*26+c] == -1) { next[u*26+c] = nodes; nodes++; } u = next[u*26+c]; } mask[u] = mask[u] | (1 << p); }
    for (c = 0; c < 26; c++) { v = next[c]; if (v == -1) { next[c] = 0; } else { queue[tail] = v; tail++; } }
    while (head < tail) { u = queue[head]; head++; for (c = 0; c < 26; c++) { v = next[u*26+c]; if (v == -1) { next[u*26+c] = next[fail[u]*26+c]; } else { fail[v] = next[fail[u]*26+c]; mask[v] = mask[v] | mask[fail[v]]; queue[tail] = v; tail++; } } }
    for (let i = 0; i < n; i++) { state = next[state*26+text[i]-97]; for (let p = 0; p < patterns; p++) { if ((mask[state] & (1 << p)) != 0) { output[count*2] = i; output[count*2+1] = p; count++; } } }
    return count;
}

Source

Primary research for the matching method. The playground uses bounded ASCII inputs and standalone teaching implementations rather than the original publication program.