Aho–Corasick Algorithm

Aho–Corasick finds occurrences of an entire dictionary of patterns during one scan of a text. It starts with a trie, then adds failure links so a mismatch can reuse a suffix of the characters already read. Output links connect states to shorter patterns that also finish at the same position. The result is exact matching, including overlaps and patterns that are suffixes of other patterns. This lesson reports every occurrence with its pattern ID and 0-based starting position, rather than only saying whether any pattern exists.

Prerequisites: Tries, queues/BFS, suffixes, and single-pattern matching such as KMP.

Build the idea

1. 1. Give every pattern an identity. Insert each lowercase pattern into a trie and store its input ID at its terminal node. A node represents the string written along the root-to-node path. Patterns that share a prefix share trie edges. Different IDs may hold identical pattern strings; their shared terminal node then stores both IDs, and each occurrence is reported for both. This program rejects empty patterns and patterns outside a–z with INVALID PATTERN followed by their ID. Empty-pattern matching at every boundary is a legitimate separate convention, but it is not hidden inside the automaton here.
2. 2. Define the state invariant and failure links. After reading a text prefix, the current state represents its longest suffix that is also a trie prefix. When a new letter cannot extend that prefix, try a shorter suffix. fail[v] points to the node representing the longest proper suffix of v's string that exists as a trie prefix. The root represents the empty suffix and fails to itself. A direct root child has failure root. These links are not parent pointers: the suffix can be located in a completely different trie branch.
3. 3. Build links breadth first. Process states by increasing trie depth, so a state's failure information is ready before processing its children. For an actual child u reached by letter c from v, set fail[u]=go[fail[v]][c]. Missing transitions are filled with the already completed transition from fail[v]. Root's missing transitions point back to root. A transition therefore handles all necessary suffix fallback in one table lookup during the text scan. This dense table costs 26 entries per state; it is convenient because the alphabet is fixed and small.
4. 4. Preserve suffix matches with output links. Reaching the state for she also means that he ends at the same text position, if both are patterns. Looking only at the current state's terminal IDs would miss he. Instead of copying every failure ancestor's output vector into every state, store out[v], the nearest terminal node on v's failure chain, or −1. It is fail[v] when that node is terminal; otherwise inherit out[fail[v]]. During matching, report the current terminal IDs and follow output links, reporting each terminal list. Each visited output node contributes at least one actual result.
5. 5. Walk the classic branching example. Insert he (ID 1), she (2), hers (3), and his (4). Scan ushers. Letter u leaves the machine at root. Then s, h, e reaches she at text index 3. Report ID 2 with start 3−3+1=1. Its output link reaches he, reporting ID 1 with start 3−2+1=2. On r, the automaton falls back from she and extends the retained he suffix to her; the following s reaches hers, reporting ID 3 at start 2. The shorter pattern is not discarded when the longer match appears.
6. 6. Why every reported occurrence is valid and none is missed. By the state invariant, each terminal suffix represented by the state or its failure ancestors is a real suffix of the text seen so far. Reporting its length therefore identifies a genuine occurrence. Conversely, any dictionary pattern ending here is a suffix of the text prefix and a trie string; it lies on the current state's suffix chain. Output links skip only nonterminal states, so they cannot skip a pattern. Completed transitions maintain the invariant by selecting the longest extendable suffix on each new letter.
7. 7. Separate scanning work from output size. This implementation streams results immediately and ends with TOTAL followed by the occurrence count. It does not keep an O(Z) result vector or copy large inherited output lists. The same text position can yield many results, and writing Z results necessarily costs Ω(Z). Nonlowercase text bytes reset the state to root, acting as separators, so a match never crosses them. An empty dictionary or empty text is valid and produces TOTAL 0. Building another dictionary requires rebuilding the completed transition tables; insertion after completion is not supported by this program.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<array>
#include<queue>
#include<string>
#include<algorithm>
using namespace std;
struct Node{
    array<int,26>next;
    int fail=0,out=-1;
    vector<int>ids;
    Node(){
        next.fill(-1);
    }
};
int main(){
    int p;
    cin>>p;
    string line;
    getline(cin,line);
    vector<Node>trie(1);
    vector<int>length(p+1);
    for(int id=1;id<=p;id++){
        string s;
        getline(cin,s);
        if(s.empty()||!all_of(s.begin(),s.end(),[](char c){
                return c>='a'&&c<='z';
            })){
            cout<<"INVALID PATTERN "<<id<<'\n';
            return 0;
        }
        int v=0;
        length[id]=(int)s.size();
        for(char ch:s){
            int c=ch-'a';
            if(trie[v].next[c]==-1){
                int fresh=(int)trie.size();
                trie[v].next[c]=fresh;
                trie.emplace_back();
            }
            v=trie[v].next[c];
        }
        trie[v].ids.push_back(id); // Duplicate strings retain distinct IDs.
    }
    queue<int>q;
    for(int c=0;c<26;c++){
        int u=trie[0].next[c];
        if(u==-1){
            trie[0].next[c]=0;
        }
        else{
            q.push(u); // Root children already have failure root and out=-1.
        }
    }
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(int c=0;c<26;c++){
            int u=trie[v].next[c];
            if(u==-1){
                // Complete missing transitions via an already processed suffix.
                trie[v].next[c]=trie[trie[v].fail].next[c];
            }
            else{
                int f=trie[trie[v].fail].next[c];
                trie[u].fail=f;
                // Link to terminal suffixes, without copying inherited ID lists.
                trie[u].out=trie[f].ids.empty()?trie[f].out:f;
                q.push(u);
            }
        }
    }
    string text;
    getline(cin,text);
    int state=0;
    long long total=0;
    for(int i=0;i<(int)text.size();i++){
        char ch=text[i];
        if(ch<'a'||ch>'z'){
            state=0;
            continue;
        }
        state=trie[state].next[ch-'a'];
        for(int v=state;v!=-1;v=trie[v].out){
            for(int id:trie[v].ids){
                cout<<id<<' '<<i-length[id]+1<<'\n';
                ++total;
            }
        }
    }
    cout<<"TOTAL "<<total<<'\n';
}

Complexity analysis

Let M be the total pattern length, S the trie-state count (S≤M+1), N the text length, and Z the number of reported ID occurrences. Dense construction takes O(M+26S), scanning/reporting O(N+Z), and storage O(26S+M) including terminal IDs and pattern lengths. The alphabet is fixed at 26, so these simplify to O(M+N+Z) time and O(M+1) space. Output size must not be omitted.

Example input and output

P on the first line; then P nonempty lowercase pattern lines; then one text line. Print each occurrence as patternID startIndex in increasing ending position, longer terminal suffixes before shorter ones, then TOTAL count. Invalid pattern input stops with INVALID PATTERN id.

Input

4
he
she
hers
his
ushers

Output

2 1
1 2
3 2
TOTAL 3

she and he both end at index 3. hers ends at index 5; all three occurrences are retained.

Practical applications

Multi-pattern dictionary search, scanning documents for keywords, recognizing forbidden substrings in DP, and matching many motifs over a fixed alphabet. For counting per pattern without printing all matches, propagate state-visit counts backward over failure links after scanning.

Check your understanding

Why does the state for she need an output link to he when both are patterns?

Put it into practice

Count occurrences of every pattern without explicitly listing each occurrence.