Aho–Corasick finds occurrences of a fixed dictionary of patterns while reading a text from left to right. We will report every occurrence: matches may overlap, and several patterns may end at the same position.
Use the dictionary D=[ab,bab,b,bc], inserted in this order, and the text T=babc. Pattern IDs start at in insertion order; text positions also start at . Patterns are nonempty, and both patterns and text use lowercase English letters. Equal dictionary entries keep separate IDs, so each is reported when that string occurs.
A trie shares the common prefixes of the patterns. Starting at the root, follow one edge per character, creating an edge when it is missing. The final vertex stores the pattern's ID and becomes a terminal vertex. A terminal can have children: the pattern b also begins bab and bc.
Write str(v) for the string on the path from the root to vertex v. The root is vertex 0 and represents the empty string ε. Vertex numbers below follow creation order; they are separate from pattern IDs.
Интерактивсанҷида бин!
During the scan, the current vertex represents the longest suffix of the text already read that is also a dictionary prefix. This is the state invariant. A complete pattern counts as one of its own prefixes; the empty suffix always qualifies, so the root covers the case when no nonempty prefix fits.
After reading ba, the state is vertex 4, although no pattern has ended there. This unfinished prefix must be retained so that the next b can complete bab.
Follow suffix links after a mismatch
After reading bab, the state is vertex 5. The next character, c, has no outgoing edge there. We must keep an ending of the text that can still be extended.
For a nonroot vertex v, its suffix link, written link(v), points to the longest proper suffix of str(v) that is represented in the trie. A proper suffix is shorter than the whole string. If no nonempty suffix qualifies, the link points to the root. Set link(0)=0 as a convention.
At vertex 5, the longest such suffix is ab, so we move to vertex 2. There is no c edge there either. Its suffix link preserves b at vertex 3, whose c edge reaches vertex 6. The new state represents bc.
The character waits while suffix links are followed; only taking a character edge consumes it. At the root, a missing edge consumes the character and leaves the state at the root. Follow that distinction in the walkthrough.
Интерактивсанҷида бин!
Why do these links find the right next state? Any nonempty useful suffix after appending a character consists of a previously useful suffix followed by that character. All previously useful suffixes are suffixes of the current longest one. Suffix links visit the represented suffixes from longest to shortest, so the first one that can extend gives the longest possible next state. No text character needs to be reread.
Check your reasoning
Read aba. After ab, the state is vertex 2. The correct suffix link keeps the suffix b at vertex 3, and the next a reaches vertex 4, representing ba.
Moving to the trie parent keeps a instead. It has no a edge, so another parent step reaches the root, and consuming a finishes at vertex 1. This is too short: ba is a longer dictionary prefix ending the text. Trie parents remove the last character; suffix links preserve an ending of the text.
Compute links and transitions recursively
The walkthrough determined the next state by trying shorter suffixes. Let go(v,c) be the state after consuming character c from state v. The trie together with these transitions is an automaton: a state and the next character determine the next state. We will compute its links and transitions recursively, storing each result when it is first needed.
The root supplies the base cases. Its existing character edges lead to its children; every missing transition returns to the root. Each root child has suffix link 0: the only shorter suffix of a one-character string is empty.
Suppose u is an actual trie child of a nonroot vertex v through character c. To find a proper suffix of str(u), shorten the parent's context first and then append c:
link(u)=go(link(v),c).
The first suffix step is necessary. Appending c directly to v would return u itself, which is not a proper suffix. The root children are handled separately because applying this formula with parent 0 would also return the child itself.
To compute go(v,c), take the actual c child if it exists. Otherwise, return 0 at the root, or recursively compute go(link(v),c) at a nonroot vertex. The character stays the same while the represented suffix becomes shorter.
Интерактивсанҷида бин!
In this construction, vertex 4 represents ba and has a suffix link to vertex 1, representing a. Both have a b child, so the suffix link of vertex 5 is vertex 2.
The two recursive functions work together: computing a link may request a transition, and computing a missing transition may request a link. Parents and proper suffixes represent shorter strings, so the recursion eventually reaches the root cases.
Use memoization to avoid repeating this work: once a link or transition has been computed, save its value and return it directly on later calls. The first request for go(5,c) resolves the suffix steps shown earlier and stores 6. Later requests reuse that result. There is no need to fill the entire transition table before scanning.
Report every pattern ending here
The current state keeps the longest useful suffix, but shorter suffixes can be complete patterns too. After reading bab, vertex 5 is terminal, and its suffix chain also reaches terminal vertices 2 and 3. Reporting only the current vertex would miss two patterns.
After consuming a character, inspect the current vertex and then follow suffix links until reaching the root. At each visited vertex, report all stored pattern IDs. A nonterminal stores no IDs, so it produces no report. Use a separate vertex variable for this traversal: the current search state must stay unchanged for the next character.
Интерактивсанҷида бин!
At text index 2, these terminals report bab on [0,2], ab on [1,2], and b on [2,2]. For a pattern of length ℓ ending at index i, its occurrence is the inclusive interval [i−ℓ+1,i].
This reports exactly the required patterns. Any pattern ending here is a dictionary prefix and a suffix of the consumed text, so it is a suffix of the current state's string. The suffix chain contains every represented suffix, so checking all its vertices finds every matching terminal. Conversely, each reported terminal is such a suffix, so it is a real occurrence.
Check your reasoning
The first b is already a match, so the modified scan resets immediately. It then reads ab, reports its matches, and resets again. It misses bab on [0,2] and bc on [2,3].
A pattern ending now may also provide context for a pattern ending later. Reporting must leave the state unchanged; the next transition decides which suffix remains useful.
C++ Implementation
Show implementation
Time and memory
Let M be the total length of the patterns, k their number, S the number of trie vertices, L≥1 the longest pattern length, n the text length, and z the number of reported occurrences, counting separate pattern IDs. Assume the dictionary contains at least one pattern. Each inserted character creates at most one vertex, so S≤M+1.
Inserting the dictionary takes O(M+26S) time, including initialization of each new vertex's transition arrays. There are S suffix links and at most 26S transition values. Memoization computes each value at most once. Each computation does constant work apart from requesting other cached values, so all link and transition computations together take O(26S) time.
Moving through the text adds O(n) work apart from those first-time computations. Reporting follows the whole suffix chain after each character. Each link strictly decreases the represented string's length, so the chain contains at most L nonroot vertices. Inspecting these vertices and printing the matches takes O(nL+z) time. Some inspected vertices are nonterminal, so this work need not be proportional to the number of matches.
The total time is O(M+26S+nL+z), or O(M+nL+z) for this fixed alphabet. The stored information needs O(26S+k) memory; each pattern ID is stored only at its own terminal. The fixed arrays in this implementation reserve O(26N) space, so choose N>M. Recursive calls may use O(L) stack space; the available call stack limits how deep the recursive version can go.
Check your reasoning
There are no matches: the pattern needs a b, but the text contains only a. After the first j≤r characters, the state is aj and the reporting loop checks j nonterminal vertices. After each of the remaining r characters, the state stays ar, so the loop checks r vertices. The total is
j=1∑rj+r2=2
Here n=2r, L=r+1, and z=0. The scan still takes Θ(r time, so it is not always . Following every suffix link can attain the bound even when nothing is reported.
You will learn
Represent several patterns in one trie and define what the current search state remembers.
Use suffix links to preserve useful suffixes after a mismatch.
Compute links and transitions recursively and report every occurrence, including overlaps.
Justify the construction, search, and memory bounds.
Think again
Suppose a missing character edge makes us move to the trie parent instead of following a suffix link, and then retry the same character. Would this preserve the state invariant? Give a counterexample using the dictionary above.
Activity
Suppose we report all patterns ending at the current position, then reset the search state to the root whenever at least one match was found. Would this still find every occurrence? Use T=babc and identify what is lost.
Extra challenge
Assume all links and transitions are already cached. Can this implementation always scan a text in O(n+z) time? For an integer r≥1, use the single pattern a and the text , where the exponent means repeated copies of the character. Find the number of matches and the exact number of nonroot vertices checked by the reporting loop.
3r2+r
.
2
)
O(n+z)
O(nL+z)
r
b
a2r
#include <bits/stdc++.h>using namespace std;const int N = 200200;const int A = 26;int nodes = 0, patterns = 0;int child[N][A], memo[N][A];int parent[N], letter[N], suff[N], len[N];vector<int> terminal[N];int add_vertex(int p, int c){ int v = nodes++; parent[v] = p; letter[v] = c; suff[v] = -1; fill(child[v], child[v] + A, 0); fill(memo[v], memo[v] + A, -1); return v;}void add_pattern(const string &s){ int id = patterns++; len[id] =(int)s.size(); int v = 0; for(char ch : s){ int c = ch - 'a'; if(child[v][c] == 0){ child[v][c] = add_vertex(v, c);} v = child[v][c];} terminal[v].push_back(id);}int go(int v, int c);int link(int v){ if(suff[v] != -1){ return suff[v];} if(v == 0 || parent[v] == 0){ return suff[v] = 0;} return suff[v] = go(link(parent[v]), letter[v]);}int go(int v, int c){ if(memo[v][c] != -1){ return memo[v][c];} if(child[v][c] != 0){ return memo[v][c] = child[v][c];} if(v == 0){ return memo[v][c] = 0;} return memo[v][c] = go(link(v), c);}void search_text(const string &text){ int v = 0; for(int i = 0; i <(int)text.size(); i++){ v = go(v, text[i] - 'a'); for(int u = v; u != 0; u = link(u)){ for(int id : terminal[u]){ cout << id << ' '<< i - len[id] + 1<< ' '<< i << '\n';}}}}