A request filter holds two hundred banned tokens (sqlmap, ../, union select). Running indexOf per token is two hundred scans of every URL. KMP per needle is the same tax: the haystack is walked once per pattern. The job is “which of these strings appear,” not “how many times can I restart the text.”

Aho-Corasick is a trie of all patterns plus KMP-style failure links — one automaton, one pass over the text. Output links chain every pattern that ends at this node. Build is proportional to total pattern length. Scan is O(n) plus the number of matches you emit.

This post is that automaton. One needle’s LPS is KMP. Same-length hashes: Rabin-Karp. Catalog: Algorithms Roadmap. It is not a regex engine, not a Bloom filter of tokens, and not a reason to re-teach trie layout beyond what Tries already owns.

Trie of needles, then fail like KMP

Insert every pattern into a trie. Each edge is one character. A node that completes a pattern stores that pattern’s id (or a list, if two patterns end together).

Failure link fail[u]: the longest proper suffix of the string spelled by u that is still a trie prefix. Same idea as lps[j - 1], on a forest. BFS from the root: for each child u -c→ v, walk fail until an edge c exists or you hit root.

static final class Node {
    final Map<Character, Node> next = new HashMap<>();
    Node fail;
    List<String> out = List.of();
}

static List<String> concat(List<String> a, List<String> b) {
    if (b.isEmpty()) {
        return a;
    }
    if (a.isEmpty()) {
        return b;
    }
    List<String> both = new ArrayList<>(a.size() + b.size());
    both.addAll(a);
    both.addAll(b);
    return List.copyOf(both);
}

static List<String> concat(List<String> a, String p) {
    return concat(a, List.of(p));
}

static Node build(List<String> patterns) {
    Node root = new Node();
    for (String p : patterns) {
        Node cur = root;
        for (int i = 0; i < p.length(); i++) {
            cur = cur.next.computeIfAbsent(p.charAt(i), k -> new Node());
        }
        cur.out = concat(cur.out, p);
    }
    Deque<Node> q = new ArrayDeque<>();
    root.fail = root;
    for (Node child : root.next.values()) {
        child.fail = root;
        q.add(child);
    }
    while (!q.isEmpty()) {
        Node u = q.removeFirst();
        for (var e : u.next.entrySet()) {
            char c = e.getKey();
            Node v = e.getValue();
            Node f = u.fail;
            while (f != root && !f.next.containsKey(c)) {
                f = f.fail;
            }
            v.fail = f.next.getOrDefault(c, root);
            if (v.fail == v) {
                v.fail = root;
            }
            v.out = concat(v.out, v.fail.out);
            q.add(v);
        }
    }
    return root;
}

concat copies two small lists. Output at v includes patterns that end exactly at v and patterns that end on the failure chain (a shorter pattern that is a suffix).

Note: A real implementation uses a 256-slot array on bytes, or an explicit alphabet map. HashMap per node is the lecture shape. fail must not loop on root’s missing edges: missing c at root stays at root and consumes the character.

Scan once

static List<String> findAll(String text, Node root) {
    List<String> hits = new ArrayList<>();
    Node u = root;
    for (int i = 0; i < text.length(); i++) {
        char c = text.charAt(i);
        while (u != root && !u.next.containsKey(c)) {
            u = u.fail;
        }
        u = u.next.getOrDefault(c, root);
        hits.addAll(u.out);
    }
    return hits;
}

Each character walks failure links a bounded number of times across the whole scan (same amortized argument as KMP’s j drops). Reporting k overlapping hits is Θ(k) extra — that is output size, not a hidden quadratic scan of the text.

Overlaps: pattern he and she in she. Both report at the e. That is the output-link job. Deduplicate later if the spec wants unique tokens.

When not to use Aho-Corasick

  • One needle. KMP or String.indexOf. The trie is ceremony.
  • Same length, hash reject is enough. Rabin-Karp with a set of hashes.
  • You needed regex. Character class, greedy quantifiers, and backreferences are not a trie of literals.
  • Approximate match. Edit distance / fuzzy SKU match is a different family.

Cheat sheet

Job:       all occurrences of many literal patterns in one text
Build:     trie + BFS failure links (KMP on a forest) + output union
Scan:      one pass; follow fail on missing edge; emit node.out
Time:      O(total pattern chars) build; O(n + hits) scan
JDK:       no AhoCorasick type; Map+queue, or a library for production
Not this:  one needle (KMP); regex; Bloom "maybe in the set"

Do:

  • Union fail.out into out at build time so the scan only reads one list.
  • Stay on root when the next character has no edge from root.
  • Count hits as output size, not as “the automaton was quadratic.”

Don’t:

  • Run KMP once per banned token on a hot path.
  • Forget that a shorter pattern can be a suffix of a longer one (output links).
  • Treat this as a regex compiler.

Wrap-up

Aho-Corasick puts every needle in one trie and wires failure links so a mismatch jumps to the longest suffix that is still a prefix of some needle. The haystack is read once. Hits ride the output lists.

The layout is a trie. The procedure is BFS fails plus a single scan. When the next job is numeric — GCD, modular pow, shuffle, a sample from a stream — leave strings and start at Euclid.

Next optional step in the series GCD by remainder, then extended coefficients. Euclid GCD: Subtract, Then Mod, Then Extended Coefficients