↩ back to Exact Match

Aho-Corasick Multi-Pattern String Matching

Knuth-Morris-Pratt finds one pattern in one text in O(n+m) time — but its own Pitfalls section admits a real limit: search for k different patterns in the same text by running KMP k separate times, and the text gets rescanned from scratch every time, O(k·(n+m)) total. Aho- Corasick fixes that by building every pattern into a single trie first, then generalizing KMP's failure-link trick from "the pattern compared against itself" to "every trie node compared against every other node" — one failure link per trie node instead of one per pattern position — so the whole text is scanned exactly once, however many patterns are loaded into the trie. The demo below builds a trie of four words (he, she, his, hers) that share several prefixes, computes nine failure links across it, then scans the text "ushers" once and correctly reports three overlapping matches — including one, "he" at index 2, that only shows up because a failure link points from one already-matched pattern straight to another.

Try it

The trie holds four fixed patterns — he, she, his, hers — chosen because they overlap in exactly the way that makes "many patterns, one automaton" concrete: he is itself a stored pattern and a prefix of hers, the same double-duty a node can have in any trie (see trie's Pitfalls). Step through two phases: first, a failure link is computed for every node, shallowest first — the exact same "longest prefix that's also a suffix" idea as KMP's LPS table, just applied to whichever pattern-prefix a trie node represents instead of one pattern compared against itself; watch the dashed lines appear on the trie one at a time. Then the automaton scans "ushers" once, left to right: a solid trie edge (a "goto") when the next character keeps it on a known path, a dashed failure-link jump when it doesn't — never a wasted look at a text character. Watch index 3: the walk lands on the node for she and reports it — and, in the same step, follows that node's own failure link up to the node for he and reports it too, because he is a suffix of the just-matched she and happens to be a stored pattern in its own right.

Why it works

Every trie node represents one specific string — the characters on the path from the root down to it. KMP's failure link for pattern position i answers "if the match breaks right after this point, what's the longest prefix of the pattern that's also a suffix of what's already matched, so comparing can resume there instead of from scratch?" Aho-Corasick asks the identical question for every trie node's own path-string: fail(v) is the trie node representing the longest proper suffix of v's path that is also some prefix stored in the trie — the longest suffix that is itself a real, walkable path from the root. Computing it needs every shallower node's failure link already finalized (the same "build in order, reuse what's known" constraint the LPS table has), so the build walks the trie shallowest-first: a node's failure link is either the root (for anything one character deep) or found by walking its parent's failure chain looking for a child with the same character — one comparison-and-possible-fallback, the same shape as KMP's own build step, just resolved through a different node's already-known failure link instead of the same pattern compared against itself.

The one genuinely new idea, since KMP only ever tracks one pattern: a node's failure link can point at a different pattern's own ending. In the demo, fail(she) = he — the trie node for she fails not to the root but directly to the node that marks the end of he. So finding she at some position means he is guaranteed to also end there, without rescanning a single character: reporting a match at any node means walking its entire failure chain back to the root and reporting every pattern-end found along the way, not just checking the current node itself (see Pitfalls for what happens when that chain-walk gets skipped).

Reference implementation

Matches the demo above — trie build, then failure-link BFS, then a single scanning pass:

class Node {
  children = new Map();
  isEnd = false;
  patterns = [];   // pattern(s) ending exactly here
  fail = null;
}

function buildTrie(patterns) {
  const root = new Node();
  for (const pat of patterns) {
    let node = root;
    for (const ch of pat) {
      if (!node.children.has(ch)) node.children.set(ch, new Node());
      node = node.children.get(ch);
    }
    node.isEnd = true;
    node.patterns.push(pat);
  }
  return root;
}

function computeFailLinks(root) {
  const queue = [];
  for (const child of root.children.values()) {
    child.fail = root;               // depth 1: nothing shorter to fall back to
    queue.push(child);
  }
  for (let qi = 0; qi < queue.length; qi++) {
    const u = queue[qi];
    for (const [c, v] of u.children) {
      let f = u.fail;
      while (f !== root && !f.children.has(c)) f = f.fail;
      const cand = f.children.get(c);
      v.fail = (cand && cand !== v) ? cand : root;
      queue.push(v);
    }
  }
}

function search(root, text) {
  const matches = [];
  let node = root;
  for (let i = 0; i < text.length; i++) {
    const c = text[i];
    while (node !== root && !node.children.has(c)) node = node.fail;
    if (node.children.has(c)) node = node.children.get(c);
    for (let t = node; t !== root; t = t.fail) {
      for (const p of t.patterns) matches.push({ pattern: p, start: i - p.length + 1, end: i + 1 });
    }
  }
  return matches;
}

The BFS in computeFailLinks has to process nodes in non-decreasing depth order — a node's own failure link depends on its parent's, and root's children start as trivial base cases. search's inner loop is the output-chain walk from the Why-it-works section: it runs every time the automaton advances, not only when node.isEnd is true, because a match further down the failure chain is just as real as one sitting on the current node.

Pitfalls

Skipping the failure-chain walk on a match silently drops matches. It's tempting to check only node.isEnd after each step, the way a single-pattern search would — but a node's failure chain can pass through other pattern-ends that are just as real. On the shipped example, an isEnd-only variant of the search above finds she and hers but silently drops he entirely: the automaton is sitting on the she node when the match happens, and she's own isEnd flag says nothing about the he pattern-end sitting one hop up its failure chain. Checked, not just asserted — an isEnd-only variant of the exact reference implementation above, run against the shipped patterns and text, returns [she@1, hers@2] instead of the correct [she@1, he@2, hers@2].

The whole point is not rescanning the text once per pattern. Running KMP once for each of the four shipped patterns against "ushers" would touch 4 × 6 = 24 character-positions across four separate passes; the automaton above scans the text once, needing only 7 transition attempts total (six characters, plus one extra failure-link hop when the walk falls off the she node looking for r). That gap only widens with more patterns — Aho-Corasick's reason to exist is that its scan cost is O(n) regardless of k, where naively repeating KMP costs O(k·n).

Building the automaton has its own upfront cost — worth it only when it's reused. Constructing the trie and computing every failure link costs O(m), where m is the combined length of all patterns, before a single text character gets scanned. For a one-off search of a single pattern against a single text, that's pure overhead over plain KMP. Aho-Corasick pays off exactly where KMP's per-pattern setup doesn't: many patterns, or the same pattern set searched against many texts (a spam filter's keyword list, an intrusion-detection signature set) — build the automaton once, then scan as many texts as needed at O(n) each with no further setup.

Complexity

Time: O(m) to build the trie and compute every failure link, where m is the total length of all patterns combined (12 characters across the four shipped patterns, collapsed onto 9 edges since he and his share a prefix) — the BFS visits each node once, and the inner while loop's total work across the whole build is bounded the same way KMP's own build is bounded, by how far the fallback pointer can retreat before it needs to advance again. Then O(n + z) to scan, where n is the text length and z is the number of matches actually reported — the automaton's position in the trie only gets shallower on a failure-link hop and only gets deeper on a goto, so (the same accounting argument KMP's Complexity section makes) the total number of hops across the whole scan is bounded by the total number of times it was able to get deeper, which is itself bounded by n. Space: O(m) for the trie and its failure links, O(1) beyond that during the scan (excluding the matches themselves) — the text is scanned once, left to right, never copied or re-read.

Aho-Corasick indexes a known set of patterns against a text scanned once. Suffix Array inverts that relationship: it indexes the text once, so that patterns nobody knew about at indexing time can still be searched cheaply later, with a pair of binary searches per query instead of a fresh scan. See Choosing an Exact-Match String Matcher for how multi-pattern search compares to the other nine exact-match entries.