Aho-Corasick Automaton: Trie + BFS Failure Links + Dictionary Suffix Links

1. The Three Structural Pillars of Aho-Corasick

Given a dictionary $\mathcal{P} = \{P_1, P_2, \dots, P_K\}$ of total length $M = \sum_{i=1}^K |P_i|$, we first insert all $P_i$ into a standard rooted Trie where the root is state $0$. Each node $u$ corresponds to a unique prefix string $S(u)$ of one or more patterns. We augment the Trie with three structures computed in a single Breadth-First Search (BFS) over the nodes by depth:

1. Failure Link ($\text{fail}[u]$): The unique Trie node $v \neq u$ maximizing $|S(v)|$ such that $S(v)$ is a proper suffix of $S(u)$. For the root and all depth-1 children of the root, $\text{fail}[u] = 0$.
2. Completed DFA Transition Table ($\text{go}[u][c]$): Instead of walking up failure links at query time with a while loop (which adds branch mispredictions and requires amortized analysis), we materialize the full transition table during BFS: $$\text{go}[u][c] = \begin{cases} \text{trie}[u][c] & \text{if child } c \text{ exists at } u \\ 0 & \text{if } u = 0 \text{ and child } c \text{ is absent} \\ \text{go}[\text{fail}[u]][c] & \text{if } u > 0 \text{ and child } c \text{ is absent} \end{cases}$$ Because $\text{depth}(\text{fail}[u]) < \text{depth}(u)$, when BFS visits node $u$, $\text{go}[\text{fail}[u]][c]$ has already been completely computed for all characters $c \in \Sigma$!
3. Dictionary Suffix Link ($\text{exit}[u]$ / Output Link): A pattern $P_j$ might be a proper substring of another pattern (e.g., $\texttt{"she"}$ and $\texttt{"he"}$ inside $\texttt{"ushers"}$). When the automaton reaches state $u = \texttt{"she"}$, we must also report $\texttt{"he"}$ at $\text{fail}[u]$. However, walking the entire $\text{fail}$ chain at every text position takes $O(\text{depth}(u))$ even when no pattern ends on that chain, degrading worst-case runtime to $O(N \cdot \max |P_i|)$. We fix this by computing $\text{exit}[u]$ during BFS: $$\text{exit}[u] = \begin{cases} \text{fail}[u] & \text{if } \text{is\_terminal}[\text{fail}[u]] = \text{true} \\ \text{exit}[\text{fail}[u]] & \text{otherwise} \end{cases}$$ Traversing $\text{exit}[u]$ jumps exclusively between terminal states that actually emit matches, guaranteeing $O(1)$ work per reported match $Z$.

2. Visual Trace: Dictionary $\{\texttt{"he"}, \texttt{"she"}, \texttt{"his"}, \texttt{"hers"}\}$

In the classic Aho-Corasick paper example below, solid arrows show Trie edges, dashed red arrows show non-root failure links $\text{fail}[u]$, and green double-bordered circles denote terminal states. Notice that state $5$ ($\texttt{"she"}$) has $\text{fail}[5] = 2$ ($\texttt{"he"}$), which is itself terminal, so $\text{exit}[5] = 2$: matching $\texttt{"she"}$ immediately emits both $\texttt{"she"}$ and $\texttt{"he"}$.

3. Production Implementation: Completed-DFA Aho-Corasick

#include <array>
#include <queue>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

class AhoCorasick {
public:
    static constexpr int ALPHA = 26;
    struct Node {
        std::array<int, ALPHA> go{};
        int fail = 0;
        int exit_link = 0;      // Nearest terminal ancestor on fail chain
        std::vector<int> pat_ids; // Pattern IDs ending exactly at this node
    };

    AhoCorasick() { nodes_.emplace_back(); }

    void insert(std::string_view pat, int id) {
        int u = 0;
        for (char ch : pat) {
            int c = ch - 'a';
            if (nodes_[u].go[c] == 0) {
                nodes_[u].go[c] = static_cast<int>(nodes_.size());
                nodes_.emplace_back();
            }
            u = nodes_[u].go[c];
        }
        nodes_[u].pat_ids.push_back(id);
    }

    void build() {
        std::queue<int> q;
        for (int c = 0; c < ALPHA; ++c) {
            int v = nodes_[0].go[c];
            if (v != 0) {
                nodes_[v].fail = 0;
                q.push(v);
            }
        }
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            int f = nodes_[u].fail;
            nodes_[u].exit_link = !nodes_[f].pat_ids.empty() ? f : nodes_[f].exit_link;

            for (int c = 0; c < ALPHA; ++c) {
                int v = nodes_[u].go[c];
                if (v != 0) {
                    nodes_[v].fail = nodes_[f].go[c];
                    q.push(v);
                } else {
                    nodes_[u].go[c] = nodes_[f].go[c];
                }
            }
        }
    }

    // Returns (end_index_in_text, pattern_id) for all occurrences in O(N + Z)
    std::vector<std::pair<int, int>> search(std::string_view text) const {
        std::vector<std::pair<int, int>> matches;
        int u = 0;
        for (int i = 0; i < static_cast<int>(text.size()); ++i) {
            u = nodes_[u].go[text[i] - 'a'];
            for (int cur = u; cur != 0; cur = nodes_[cur].exit_link) {
                for (int pid : nodes_[cur].pat_ids) {
                    matches.emplace_back(i, pid);
                }
            }
        }
        return matches;
    }

private:
    std::vector<Node> nodes_;
};