Aho-Corasick Automaton: Core Principles and Implementation for Efficient Multi-pattern Matching

Core Logic and Mathematical Principles

The essence of the Aho-Corasick Automaton (AC Automaton) is to forcefully adapt the mismatch transition concept of the KMP algorithm into a trie structure (Trie Tree), thereby constructing a deterministic finite automaton (DFA) for multi-pattern string matching. It can perform full multi-pattern matching of several patterns within a single text string in $O(N + \\sum L_i)$ time complexity.

1. Mathematical Definition of the $ ext{fail}$ Pointer

Let the string corresponding to a node $u$ in the Trie tree be $S_u$. The fail pointer of this node, $fail[u]$, points to node $v$ if and only if: $S_v$ is the longest proper suffix of $S_u$ that can be matched in the entire Trie tree.

2. Mathematical Reduction of State Transition and Trie Graph Optimization

In a traditional Trie tree with a $ ext{fail}$ pointer, if the current state $u$ lacks a transition edge for character $c$, one must backtrack along $fail[u]$ to the root node until finding an edge with character $c$. This backtracking can degrade the time complexity of a single state transition to $O(\text{Depth})$ in the worst case.

The AC Automaton employs Trie Graph optimization to break this efficiency bottleneck: For state $u$ and its incoming character $c$:

• If a transition edge exists ($nxt[u][c] \neq 0$): the fail pointer of this child node directly inherits the fail state of the current node:

$$fail[nxt[u][c]] = nxt[fail[u]][c]$$

• If a transition edge does not exist ($nxt[u][c] == 0$): forcefully redirect the missing virtual edge to the corresponding transition of its fail node:

$$nxt[u][c] = nxt[fail[u]][c]$$

Through this space-for-time path compression, the Trie tree is restructured into a seamless DFA. Any state can perform an accurate state transition in $O(1)$ time when facing any character, eliminating all backtracking iterations.

State Design and Algorithm Derivation

1. Breadth-First Search (BFS) Layered Propagation of the $ ext{fail}$

Since the length of the longest proper suffix must be strictly less than the current string's length, the computation of the $ ext{fail}$ pointer must strictly adhere to the bottom-up propagation principle of longer factors. Utilizing a queue for breadth-first traversal is the optimal solution.

1. Initialization of Second Layer Nodes: Forcefully enqueue all direct child nodes of the root node (depth 1 nodes) and set their $fail$ pointers to 0.
2. State Propagation: Dequeue the front node $u$. Iterate over all character sets $c \in [0, \Sigma-1]$:

• If $nxt[u][c]$ exists, set the child node as $v$. Point $fail[v]$ to $nxt[fail[u]][c]$, and enqueue $v$.
• If $nxt[u][c]$ does not exist, perform path compression: nxt[u][c] = nxt[fail[u]][c].

2. Mathematical Differences in Text String Matching and Counting

When running the AC Automaton on a single text string $S$, the pointer $u$ jumps along the DFA with the text characters. Each time a node $u$ is reached, it not only indicates that the pattern string ending at $u$ is triggered, but also all ancestor nodes reachable through the $fail$ pointer are simultaneously triggered. Therefore, we need to either harvest the exist markers along the $fail$ chain or establish a $ ext{fail}$ tree for contribution accumulation through topological sorting (advanced optimization).

C++ Standard Source Code (NOIP Style)

Below is a standard implementation of the AC Automaton utilizing Trie Graph optimization.

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

const int MAX_NODES = 500005; // Upper limit of total character nodes

int nxt[MAX_NODES][26];
int fail[MAX_NODES];
int cnt_match[MAX_NODES]; // Record the number of pattern strings ending at this node
int cnt = 0;             // Node 0 strictly acts as the root node

// 1. Standard multi-pattern string injection into Trie tree
void insert(const string& s) {
    int u = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (!nxt[u][c]) {
            nxt[u][c] = ++cnt;
        }
        u = nxt[u][c];
    }
    cnt_match[u]++; // Mark the end of this pattern string
}

// 2. Core: Build the AC Automaton's Trie Graph and fail pointers
void build_ac() {
    queue<int> q;

    // Special handling for second layer nodes to prevent fail pointer self-loop deadlock
    for (int i = 0; i < 26; ++i) {
        if (nxt[0][i]) {
            fail[nxt[0][i]] = 0;
            q.push(nxt[0][i]);
        }
    }

    // BFS Layered Propagation
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int i = 0; i < 26; ++i) {
            if (nxt[u][i]) {
                fail[nxt[u][i]] = nxt[fail[u]][i]; // Core transition: inherit the longest common proper suffix state
                q.push(nxt[u][i]);
            } else {
                nxt[u][i] = nxt[fail[u]][i]; // Core optimization: compress nonexistent edges to point to fail node transitions, achieving O(1) jump
            }
        }
    }
}

// 3. Core: Retrieve the total frequency of triggered multi-pattern strings in a single text string
int query(const string& t) {
    int u = 0;
    int total_ans = 0;

    for (char ch : t) {
        int c = ch - 'a';
        u = nxt[u][c]; // Regardless of whether this transition is a real edge or a compressed virtual edge, it can directly transition in $O(1)$

        // Along the fail chain, clear all pattern strings that can be matched at the current position
        for (int t_u = u; t_u && cnt_match[t_u] != -1; t_u = fail[t_u]) {
            total_ans += cnt_match[t_u];
            cnt_match[t_u] = -1; // Critical pitfall: if the problem requires "how many kinds" appear, after harvesting, must set to -1 to prune and prevent time degradation
        }
    }
    return total_ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (cin >> n) {
        string pattern;
        for (int i = 0; i < n; ++i) {
            cin >> pattern;
            insert(pattern);
        }

        build_ac();

        string text;
        cin >> text;
        cout << query(text) << "\n";
    }
    return 0;
}

NOIP Practical Pitfall Guide

1. Misplacement of Second Layer Nodes Leading to Full RE or Infinite Loop

When initializing in build_ac, absolutely do not enqueue the root node 0 itself to propagate its own child nodes. If you directly enqueue 0, during the execution of fail[nxt[0][i]] = nxt[fail[0]][i], since fail[0] defaults to 0, it will lead to a catastrophic self-loop in the fail pointer calculation logic of the second layer nodes (i.e., fail[v] = v), causing subsequent queries to instantly fall into an infinite loop or stack overflow RE when traversing the fail chain.

2. Ignoring the Violent Jump of the fail Chain in query Leading to "Pseudo $O(N)$" Time Degradation (TLE)

Many competitors mistakenly believe that the time complexity of the AC Automaton with Trie Graph optimization is strictly $O(N)$. This is a fatal misconception. The Trie Graph only ensures that the pointer u during the outer traversal of the text string transitions in $O(1)$; however, in the inner loop, for (int t_u = u; t_u; t_u = fail[t_u]), this code still exists. If extreme malicious data is constructed (e.g., patterns a, aa, aaa, aaaa, with a long text string of a), each state transition requires forcibly traversing the fail chain to the root node, degrading the single complexity to $O(\text{total length of patterns})$, leading the entire program to suffer from TLE. Breaking Strategy: If the problem only requires counting whether each string appears, it must be like the source code, marking with -1 after scanning to block and prune. If precise statistics of each string's occurrence are required, do not violently jump the fail chain in query; rather, only mark the frequency increment at the current node, and finally extract all nodes to accumulate contributions in a topological sort (topological order bottom-up) using the fail pointers to perform a prefix sum.

Classic NOIP/Luogu Problems

1. Luogu P3808 [Template] AC Automaton (Simple Version)

• Problem Description: Given $N$ pattern strings and a text string $M$, find how many distinct pattern strings appeared in the text string.
• Essential Problem: Benchmark problem for multi-pattern string set coverage retrieval.
• Core Solving Idea: As shown in the source code above. Construct all pattern strings into an AC Automaton and perform a single scan of the text string. During the scan, retrieve all triggered end markers along the fail pointer through the inner loop and use -1 for memoization pruning to prevent efficiency collapse due to repeated access to the same path.

2. Luogu P3796 [Template] AC Automaton (Enhanced Version)

• Problem Description: Given $N$ pattern strings and a text string $M$, find which pattern strings appeared the most and output them along with their respective maximum occurrence counts in the input order.
• Essential Problem: Accurate non-backtracking statistics of multi-state trigger frequencies.
• Core Solving Idea:

1. Since we need to count the exact occurrence of each string, we cannot simply count at the leaf nodes of the Trie tree but should record which input pattern string number id corresponds to this node.
2. During the query scan of the text string, do not jump the fail chain; directly increment the counter at this node with ans[u]++.
3. After scanning, we know that all fail pointers form a tightly structured tree topology (with the root node being 0). Accumulate the ans values of child nodes to their fail parent nodes: ans[fail[u]] += ans[u].
4. Finally, map back to the pattern string numbers to find the maximum value and output them as required, perfectly avoiding time degradation traps.