Aho-Corasick — Missing Output Links Drop 40% of Matches

Running KMP once per pattern scales linearly with pattern count. For 10,000 signatures on a 1 Gbps traffic stream, that's physically impossible at line rate. Aho-Corasick solves this by building a single deterministic automaton from all patterns upfront, then running the text through it exactly once — regardless of whether you have 10 patterns or 100,000.

Published in 1975 by Alfred Aho and Margaret Corasick at Bell Labs, the algorithm generalizes KMP's failure function to a trie. The failure links in Aho-Corasick are KMP failure function values applied across a shared prefix tree. If you understand why KMP doesn't restart from position zero on a mismatch, Aho-Corasick failure links will feel immediately familiar — the mechanics are identical, just extended to a tree instead of a linear string.

The trade-off is upfront preprocessing cost and a hard constraint: exact strings only. No wildcards, no quantifiers, no character classes. That limitation is precisely why it's fast — and precisely why it's the right tool when you need raw throughput on known, fixed signatures. When you need regex semantics at scale, you reach for Hyperscan. When you need to match a fixed dictionary of strings against a stream, you reach for Aho-Corasick.

How Aho-Corasick Finds All Patterns in One Pass

Aho-Corasick is a string-searching algorithm that locates all occurrences of a finite set of patterns in a text in O(n + m + z) time, where n is text length, m is total pattern length, and z is total matches. Its core mechanic is a trie augmented with failure links — pointers that redirect a mismatch to the longest proper suffix that is also a prefix of some pattern. This transforms naive backtracking into a single linear scan.

Construction builds the trie, then BFS-computes failure links: each node's failure link points to the node representing the longest suffix of its string that exists in the trie. During search, on a character mismatch, the algorithm follows the failure link instead of resetting to root. Output links (dictionary suffix links) chain failure links to collect all patterns ending at the current position — missing these drops matches, often 40% or more in practice.

Use Aho-Corasick when you need to detect multiple patterns simultaneously, such as in intrusion detection systems (Snort), content filters, or genomic sequence matching. It is optimal for static pattern sets and streaming text. Do not use it for single-pattern search — Boyer-Moore or KMP is simpler and faster.

Building the Trie

The first step is inserting all patterns into a trie — a prefix tree where each node represents a character on the path from root to some suffix. Nodes that complete a full pattern are marked as output nodes, storing the pattern ID (or the pattern string itself, depending on what you need to report).

The key property of the trie is prefix sharing. If two patterns share a common prefix, they share the corresponding nodes in the tree. Patterns 'http' and 'https' share five nodes — you only pay for the single divergent node at the 's'. A collection of 10,000 URL patterns with common prefixes like '/api/v1/', '/api/v2/' might compress to 2,000 trie nodes. A collection of 10,000 random hex strings compresses to almost nothing — nearly every character is a new branch.

The implementation below uses a list of dictionaries for the goto table. Each dictionary maps a character to the next node index. This is readable and correct for moderate-sized pattern sets with ASCII input. It breaks down with large alphabets (UTF-8 codepoints as characters rather than bytes) or very large node counts — at that scale the per-dict overhead in Python becomes a memory and cache-pressure problem. The correct fix in that scenario is pyahocorasick, which uses a C-backed double-array trie where each transition is a direct array index.

# io.thecodeforge.algo.aho_corasick_trie
from collections import deque


class AhoCorasick:
    """Aho-Corasick automaton for multi-pattern exact string matching.

    Build once with add_pattern() + build(), then call search() repeatedly.
    The automaton is immutable after build() — adding patterns after build
    requires a full rebuild.
    """

    def __init__(self):
        # goto[node][char] = next_node_id
        # Node 0 is the root. All failure links eventually reach 0.
        self.goto: list[dict[str, int]] = [{}]
        self.fail: list[int] = [0]
        # output[node] = list of pattern IDs that end at this node
        # After build(), also includes IDs inherited from failure link targets
        self.output: list[list[int]] = [[]]

    def add_pattern(self, pattern: str, pid: int) -> None:
        """Insert a pattern into the trie. Call before build()."""
        node = 0
        for ch in pattern:
            if ch not in self.goto[node]:
                # Allocate a new node
                self.goto.append({})
                self.fail.append(0)
                self.output.append([])
                self.goto[node][ch] = len(self.goto) - 1
            node = self.goto[node][ch]
        self.output[node].append(pid)


# --- Usage example ---
ac = AhoCorasick()
patterns = ['he', 'she', 'his', 'hers']
for i, p in enumerate(patterns):
    ac.add_pattern(p, i)

print(f'Trie nodes: {len(ac.goto)}')  # 11
# 'he', 'she' share no prefix with 'his', 'hers'
# 'his' and 'hers' share 'h' — one node
# Total unique prefixes across all four patterns: 11 nodes including root

Building Failure Links

Failure links are what separate Aho-Corasick from a trie with a linear scan per pattern. For each trie node v — reached by the path of characters representing some string S — the failure link points to the node representing the longest proper suffix of S that is also a valid prefix of some pattern in the set. If no such suffix exists, the failure link points to the root.

This is KMP's failure function, applied to every node in the trie simultaneously. When the search is at node v and the next character has no goto edge, following fail[v] gives you the best valid position to continue from — no characters rescanned, no match opportunity lost.

Failure links are built with BFS from the root, level by level. The ordering is non-negotiable: 1. Root's direct children all get fail = root (the root is its own failure destination) 2. For each node v at depth d, and each character c where v has a child: that child's failure link is goto(fail[v], c). This requires fail[v] to already be computed — which is why BFS level-ordering works and DFS does not. 3. The goto shortcut step: for characters not present in v's children, set goto[v][c] = goto[fail[v]][c]. This precomputes the 'where would failure take me?' step for every character, so search never needs to traverse a chain of failure links — one goto lookup is always sufficient.

The output merge happens here too, in the same BFS pass: self.output[child] += self.output[self.fail[child]]. This is covered in depth in the Output Links section, but it belongs in the build step — not in the search loop.

# io.thecodeforge.algo.aho_corasick_fail
# This method is added to the AhoCorasick class defined in aho_corasick_trie.py

    def build(self) -> None:
        """Build failure links and goto shortcuts using BFS.

        Must be called once after all patterns are added via add_pattern().
        After this call, the automaton is ready for search().
        Adding new patterns after build() requires a full rebuild.
        """
        q: deque[int] = deque()

        # Root's direct children: failure link = root (node 0)
        # Also compute goto shortcuts for root: any character not in root's
        # children loops back to root (same as KMP resetting to start)
        all_chars = set(ch for node in self.goto for ch in node)
        for ch in all_chars:
            if ch not in self.goto[0]:
                self.goto[0][ch] = 0  # Shortcut: unknown char at root -> stay at root

        for ch, child in list(self.goto[0].items()):
            if child != 0:  # Skip the shortcuts we just added
                self.fail[child] = 0
                q.append(child)

        while q:
            node = q.popleft()
            for ch, child in list(self.goto[node].items()):
                # Compute failure link for child:
                # Follow fail[node] until we find a node with a goto for ch
                # (or reach root). With root shortcuts, this is always O(1).
                f = self.fail[node]
                self.fail[child] = self.goto[f].get(ch, 0)

                # Guard against self-referential failure links
                # (can occur at root level without the shortcut above)
                if self.fail[child] == child:
                    self.fail[child] = 0

                # CRITICAL: merge output from failure link target
                # Without this line, patterns that are suffixes of other patterns
                # are silently dropped from results
                self.output[child] = self.output[child] + self.output[self.fail[child]]

                # Compute goto shortcuts for child:
                # For every character in the alphabet that child has no edge for,
                # precompute where failure would take us. This makes search O(1) per char.
                for c in all_chars:
                    if c not in self.goto[child]:
                        self.goto[child][c] = self.goto[self.fail[child]].get(c, 0)

                q.append(child)

Searching the Text

With failure links and goto shortcuts built, searching is a single linear pass through the text. For each character you follow a goto edge — which is O(1) because shortcuts were precomputed during build — land on the next node, and check its output list. The output list at each node already contains matches inherited from failure link targets, because the build step merged them. There is no chain to follow during search, no backtracking, no lookahead.

The search loop is simple enough to fit in a few lines. That simplicity is the result of doing all the hard work during build — the automaton encodes every mismatch-recovery decision as a precomputed edge, so the search just follows edges and collects outputs.

# io.thecodeforge.algo.aho_corasick_search
# This method is added to the AhoCorasick class

    def search(self, text: str) -> list[tuple[int, int]]:
        """Search text for all patterns. Returns (end_pos, pattern_id) pairs.

        end_pos is the index of the last character of the match.
        start_pos = end_pos - len(patterns[pattern_id]) + 1

        Requires build() to have been called first.
        Time complexity: O(n + k) where n = len(text), k = match count.
        """
        node = 0
        results: list[tuple[int, int]] = []
        for i, ch in enumerate(text):
            # With goto shortcuts, this is always a single dict lookup — O(1)
            # No failure link chain traversal needed during search
            node = self.goto[node].get(ch, 0)
            # output[node] already includes matches from failure link targets
            # — the build step merged them. No additional chain traversal here.
            for pid in self.output[node]:
                results.append((i, pid))
        return results


# --- Full example ---
ac = AhoCorasick()
patterns = ['he', 'she', 'his', 'hers']
for i, p in enumerate(patterns):
    ac.add_pattern(p, i)
ac.build()

matches = ac.search('ahishers')
for end, pid in matches:
    p = patterns[pid]
    print(f"'{p}' ends at index {end} (starts at {end - len(p) + 1})")

Complexity Analysis

Let n = text length, m = sum of all pattern lengths, k = total number of matches found.

Trie construction: O(m) — insert each character of each pattern once Failure link construction: O(m × |Σ|) with goto shortcut precomputation, where |Σ| is the alphabet size. For ASCII (|Σ| = 128) this is O(128m), which is O(m) with a constant factor. For full Unicode codepoints (|Σ| ≈ 140,000) this factor becomes significant — byte-level tries (|Σ| = 256) are the standard production choice for Unicode text. Search: O(n + k) — each character examined once, each match reported once Total: O(n + m + k)

This is provably optimal — you must read all input and report all matches. The critical observation is that pattern count does not appear in the search complexity. Searching with 10,000 patterns takes the same time as searching with 1, once the automaton is built. That is the entire value proposition of the algorithm.

The alphabet size factor in failure link construction is worth understanding before deployment. A byte-level trie (|Σ| = 256) has a constant factor roughly 10x larger than an ASCII lowercase trie (|Σ| = 26). For most production pattern sets this is absorbed — the build runs once and the search runs millions of times. But for very large pattern sets (millions of patterns) with byte-level alphabets, the build step can take tens of seconds. Profile it before assuming it's negligible.

Output Links — The Bug That Silently Drops Matches

Output links deserve their own section because they are the single most common source of production bugs in Aho-Corasick implementations, and because the failure mode is the worst kind: silent, correct-looking, and only detectable by knowing what should have been found.

The problem arises with overlapping patterns. Consider patterns 'she' and 'he'. In the trie, 'she' is represented by the path root → s → h → e. The node at the end of this path has fail pointing to the node representing 'he' (root → h → e), because 'he' is the longest suffix of 'she' that is also a pattern prefix. When the search reaches the 'she' terminal node, it should report both 'she' and 'he' — 'she' because that pattern ends here, and 'he' because the text at this position also ends a valid match for 'he'.

Without output merging, only 'she' is reported. The failure link is structurally correct — it points to the right node. But the output list at the 'she' terminal node only contains 'she'. The output at the 'he' node was never propagated.

The fix is one line in the BFS build loop: self.output[child] += self.output[self.fail[child]]. This propagates the output list from the failure link target into the current node at build time, so the search loop never needs to traverse failure links to collect outputs — it just reads the output list directly.

This is not a fringe case. Any pattern set that contains a pattern which is a suffix of another pattern exhibits this relationship. In URL pattern sets, '/api' is a suffix of '/internal/api'. In signature databases, short attack signatures are frequently substrings of longer ones. In content moderation, short slur variants are often substrings of longer ones. The overlap is the norm, not the exception.

# io.thecodeforge.algo.output_links_demo
# Side-by-side demonstration: broken vs correct output merging
# Both versions build failure links correctly — only output handling differs

from collections import deque


def build_broken(ac) -> None:
    """BROKEN: failure links correct, output merging missing.
    The automaton navigates correctly but silently drops suffix-pattern matches.
    """
    q: deque[int] = deque()
    for ch, child in ac.goto[0].items():
        ac.fail[child] = 0
        q.append(child)
    while q:
        node = q.popleft()
        for ch, child in ac.goto[node].items():
            f = ac.fail[node]
            while f != 0 and ch not in ac.goto[f]:
                f = ac.fail[f]
            ac.fail[child] = ac.goto[f].get(ch, 0)
            if ac.fail[child] == child:
                ac.fail[child] = 0
            # BUG: the following line is missing
            # ac.output[child] += ac.output[ac.fail[child]]
            q.append(child)


def build_correct(ac) -> None:
    """CORRECT: failure links and output merging both present."""
    q: deque[int] = deque()
    for ch, child in ac.goto[0].items():
        ac.fail[child] = 0
        q.append(child)
    while q:
        node = q.popleft()
        for ch, child in ac.goto[node].items():
            f = ac.fail[node]
            while f != 0 and ch not in ac.goto[f]:
                f = ac.fail[f]
            ac.fail[child] = ac.goto[f].get(ch, 0)
            if ac.fail[child] == child:
                ac.fail[child] = 0
            # CORRECT: propagate outputs from failure link target
            ac.output[child] = ac.output[child] + ac.output[ac.fail[child]]
            q.append(child)


# Test: patterns ['she', 'he'], text 'she'
# Expected matches: both 'she' (ends at index 2) and 'he' (ends at index 2)
# Broken result:  [(2, 'she')]          — 'he' silently dropped
# Correct result: [(2, 'she'), (2, 'he')] — both reported

Why Your Goto Statement Will Corrupt Multi-Pattern Search State

Your failure links are built, your trie is solid. Now you hit the text character by character. The textbook says 'follow goto links.' But you forgot one thing: the state machine is a finite automaton. It has no stack. If you write a goto() function that naively walks failure pointers on every mismatch, you just swapped O(n) matching for O(n * L) worst-case where L is the pattern depth. That kills you on 100KB streams with 10,000 patterns. The fix? Precompute the transition table. For each node and each character in the alphabet, store the final state after following failure links recursively. This is the Aho-Corasick automaton — a proper DFA. The goto function is only for building. During search, you jump directly. No recursion. No loops. One table lookup per character. This is not optimization; it's correctness under load. Production systems that skip this step silently drop matches when the failure chain grows deep. Don't be that team.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class BuildTransitionTable {
    static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        TrieNode fail;
        boolean isEnd;
    }

    // Precompute full transition table for all ASCII chars
    static Map<Character, TrieNode>[] buildTransitions(TrieNode root, int maxNodes) {
        Map<Character, TrieNode>[] trans = new HashMap[maxNodes];
        Queue<TrieNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TrieNode node = queue.poll();
            Map<Character, TrieNode> row = new HashMap<>();
            for (char c = 0; c < 128; c++) {
                TrieNode next = node.children.getOrDefault(c, root);
                // If next is root, follow failure chain of node for c
                if (next == root && node != root) {
                    TrieNode fail = node.fail;
                    while (fail != root && !fail.children.containsKey(c)) {
                        fail = fail.fail;
                    }
                    next = fail.children.getOrDefault(c, root);
                }
                row.put(c, next);
            }
            trans[node.hashCode() % maxNodes] = row; // simplified index
            queue.addAll(node.children.values());
        }
        return trans;
    }
}

Output Links Are Not Optional — Here's Why You Miss 'he' In 'she'

You built failure links. You built the trie. You search 'she' against patterns ['he', 'she', 'his', 'hers']. The automaton lands on node 'e' after 'sh_e'. But did you check if that node is an end node for 'he'? No, because the word 'he' ends at a different node deeper in the trie. The match is silently dropped. This is the output link bug. Output links are additional pointers from a node to the next node in the failure chain that marks the end of a pattern. They are not failure links. Failure links point to the longest proper suffix. Output links point to the next pattern-ending suffix. Without them, you only report matches when the current node itself is a pattern end. You miss all patterns that are suffixes of the current match. In production, this means false negatives on substrings like 'abc' in 'xabc' when 'bc' is also a pattern. The fix: after building failure links, walk each node's failure chain and store a reference to the first node that is a pattern end. Then during search, after every character, follow output links and report all matches. This is a one-time O(states) build cost that saves you from silent data corruption.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class BuildOutputLinks {
    static class TrieNode {
        TrieNode fail;
        TrieNode output;  // next pattern-ending node in failure chain
        boolean isEnd;
        String word;
        Map<Character, TrieNode> children = new HashMap<>();
    }

    static void buildOutputLinks(TrieNode root) {
        Queue<TrieNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TrieNode node = queue.poll();
            // Set output: if failure node is end, point to it; else inherit failure's output
            if (node.fail != null && node.fail.isEnd) {
                node.output = node.fail;
            } else if (node.fail != null) {
                node.output = node.fail.output;
            }
            for (TrieNode child : node.children.values()) {
                queue.add(child);
            }
        }
    }

    static List<String> searchWithOutput(String text, TrieNode root) {
        List<String> matches = new ArrayList<>();
        TrieNode current = root;
        for (char c : text.toCharArray()) {
            current = current.children.getOrDefault(c, root);
            // Report all matches via output links
            TrieNode report = current;
            while (report != null) {
                if (report.isEnd) matches.add(report.word);
                report = report.output;
            }
        }
        return matches;
    }
}

Dictionary Size Kills Your Trie — Why You Need A Compressed Automaton For 100K Patterns

You have 100,000 patterns. Each pattern averages 10 characters. Your trie has 1 million nodes. Each node has a HashMap<Character, TrieNode>. That's 1 million HashMap objects. At 48 bytes overhead each (Java 17+), that's 48 MB just for object headers. Plus entries, plus char keys, plus references. You're looking at 200+ MB for a single trie. Production servers will OOM or swap. The fix: compress the trie into a single int array. Store transitions in a flat array of size |states| |alphabet|. Or use double-array trie (DAT) structure. But even simpler: use adjacency list with edges stored as parallel arrays: base array for offset, next array for sibling links. This is what Aho-Corasick in Snort and ClamAV does. For Java, use a single int[] for transitions where state i transition for character c is at index i 128 + c. This is 1 MB for 1000 states, 128 MB for 100K states — still cheaper than HashMap. Yes, you waste space for unused characters. But cache locality crushes pointer chasing. Your CPU prefetcher loves contiguous memory. Your garbage collector hates 1 million small objects. Do the math. Build for scale from day one.

// io.thecodeforge — dsa tutorial

import java.util.Arrays;

public class CompressedAutomaton {
    private final int[] transitions; // flat array: [state][char] -> nextState
    private final int alphabetSize;
    private int stateCount;

    public CompressedAutomaton(int maxStates, int alphabetSize) {
        this.alphabetSize = alphabetSize;
        this.transitions = new int[maxStates * alphabetSize];
        Arrays.fill(transitions, -1); // -1 means no transition
        this.stateCount = 1; // root at state 0
    }

    public void addTransition(int fromState, char ch, int toState) {
        transitions[fromState * alphabetSize + ch] = toState;
    }

    public int nextState(int state, char ch) {
        int idx = state * alphabetSize + ch;
        return (transitions[idx] != -1) ? transitions[idx] : 0; // fallback to root
    }

    public int newState() {
        return stateCount++;
    }

    // Usage: for ASCII, alphabetSize=128, maxStates=patternTotalChars+1
    // Build failure links on top of this structure
}

Why Most Implementations Die on Large Texts — The Hidden Cost of Failure Link Traversal

You've built a trie. You've wired failure links. But when you hit a mismatch, do you really think jumping up through a chain of failure links is cheap? That's O(|pattern|) per character. When the text is 10 million characters and you've got 100,000 patterns, you just signed up for a trillion operations.

The fix is the output link — a direct pointer to the nearest node that has a match. No chain. No while-loop. One jump. This is the single most important optimization in production Aho-Corasick. Without it, your search degrades to O(text_length * max_depth) instead of O(text_length + total_matches).

Build output links during failure link generation. Each node stores a reference to the next ancestor that represents a completed pattern. When you follow failure links during search, you only do one extra hop. Teams that skip this see 500% latency spikes under load. Senior devs call this the "pay for what you use" — you paid to build the trie, don't pay again every time you search.

// io.thecodeforge — dsa tutorial

class AhoCorasick {
    static class Node {
        Node[] children = new Node[26];
        Node fail, output;
        int patternId = -1;
    }

    Node root = new Node();

    void buildOutputLinks() {
        Queue<Node> q = new LinkedList<>();
        for (Node n : root.children) if (n != null) q.add(n);
        while (!q.isEmpty()) {
            Node curr = q.poll();
            curr.output = (curr.fail.patternId != -1) ? curr.fail : curr.fail.output;
            for (int i = 0; i < 26; i++) {
                if (curr.children[i] != null) q.add(curr.children[i]);
            }
        }
    }

    void search(String text) {
        Node curr = root;
        for (char c : text.toCharArray()) {
            int idx = c - 'a';
            while (curr != root && curr.children[idx] == null) curr = curr.fail;
            curr = (curr.children[idx] != null) ? curr.children[idx] : root;
            for (Node out = curr.output; out != null; out = out.output) {
                System.out.println("Match at index " + text.indexOf(c) + ": pattern " + out.patternId);
            }
        }
    }
}

The One Search Architecture That Survives 10GB Texts — Streaming, Not Buffering

Most implementations load the entire text into memory. That's the naive approach. Works for your 2KB test file. Fails when your log pipeline streams 10GB/hour. Real systems use a sliding window — process characters one by one without holding the whole text.

Your automaton state is the only state you need. It's a single integer (node index). The text can be a memory-mapped file, a socket, or stdin. Each character updates the current node. When you hit a match, you report the current position minus the pattern length. That's it.

The trap? Character-by-character I/O is slow unless you buffer reads in 64KB chunks. Use a BufferedInputStream or similar. Never use Reader.read() in a loop. Batch your input, stream your state. The automaton doesn't care where the text came from — it just needs one character at a time.

In production, this means you can grep 100GB log files without running out of memory. The automaton itself takes O(total_pattern_length) memory — that's your real limit. Text size is irrelevant.

// io.thecodeforge — dsa tutorial

import java.io.*;

class StreamingAho {
    final Node root = new Node();
    long position = 0;

    void search(InputStream in) throws IOException {
        BufferedInputStream buf = new BufferedInputStream(in, 65536);
        Node curr = root;
        int b;
        while ((b = buf.read()) != -1) {
            int idx = b - 'a';
            while (curr != root && curr.children[idx] == null) curr = curr.fail;
            curr = (curr.children[idx] != null) ? curr.children[idx] : root;
            if (curr.patternId != -1) {
                System.out.println("Found pattern " + curr.patternId + " at position " + (position - curr.depth));
            }
            position++;
        }
    }
}

Searching in the Automaton — How Match State Progresses

The searching stage is where the Aho-Corasick automaton processes the input text and collects matches. You start at the root node and iterate character by character. For each character, you follow a transition from the current node — either along a direct child edge (if one exists for that character) or by following failure links until you find a node that has the required transition, or you hit the root. This traversal across failure links is where hidden performance costs appear: if you chain-fail repeatedly on every mismatch, you turn a linear algorithm into something worse. Once you land on a node (after possibly traversing failures), you then check whether that node (or any node reachable via output links) represents a complete pattern. Every such node is a match, and its index in the pattern list is recorded along with the current text position. The text is consumed in a single pass — no backtracking. This is why Aho-Corasick is O(n) in search time, but only if failure link traversal is amortized constant. The moment your failure graph is deep and you recompute paths repeatedly, the theoretical guarantee breaks.

// io.thecodeforge — dsa tutorial
public int search(String text, TrieNode root, List<String> patterns) {
    TrieNode cur = root;
    int matchCount = 0;
    for (int i = 0; i < text.length(); i++) {
        char c = text.charAt(i);
        while (cur != root && !cur.children.containsKey(c))
            cur = cur.fail;
        if (cur.children.containsKey(c))
            cur = cur.children.get(c);
        TrieNode tmp = cur;
        while (tmp != root && tmp.output != -1) {
            System.out.println("Match '" + patterns.get(tmp.output) + "' at pos " + (i - patterns.get(tmp.output).length() + 1));
            matchCount++;
            tmp = tmp.outputLink;
        }
    }
    return matchCount;
}

Matching Stage — Why You Can't Stop at the First Hit

Once you land on a node during search, the matching stage begins. The naïve approach checks only the current node for a pattern ending at that position. But Aho-Corasick's power — and its trap — is that a single node may be the endpoint for multiple patterns. For example, after matching 'he' in 'she', you must also report 'he' from the node reached after 'h' and 'e', even if 'he' was not the initial pattern stored. This is the job of output links: they chain together all patterns that end at the same text position via suffix relationships. In the matching stage, after you locate a node that ends a pattern, you follow the output chain and report every pattern whose index is stored along that chain. A common bug is to stop after reporting the first pattern and break the inner loop. That drops matches silently. The correct implementation uses a while loop that walks the output link chain until reaching the root. Each iteration reports one pattern. This adds at most O(k) per text position where k is the number of patterns ending at that position, but in practice k is small. Neglecting output links transforms your automaton into a broken dictionary that misses overlapping patterns.

// io.thecodeforge — dsa tutorial
void reportMatches(TrieNode node, int pos, List<String> patterns) {
    TrieNode chain = node;
    while (chain != root && chain.output != -1) {
        System.out.println("Match: " + patterns.get(chain.output) + " at " + (pos - patterns.get(chain.output).length() + 1));
        chain = chain.outputLink;
    }
}