Published by Dimitris Kougioumtzis · Updated
Build a trie, compute failure links breadth first, and report every terminal pattern including suffix matches and duplicates.
Insert every pattern into a shared trie. Compute failure links in breadth-first order and inherit output IDs from each failure target. Scan the text once, following fallback transitions and reporting all matching pattern IDs.
When to use Aho-Corasick multiple-pattern matching
Searching one text for a small dictionary of keywords, including overlapping matches.
Choosing an alternative
KMP preprocesses one pattern. Aho-Corasick shares prefixes across a dictionary and keeps suffix matches through failure links.
Worked example: input and state changes
Example input
ushers | he,she,s
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Start with the root.
State at this checkpoint
{ "values": [ "root" ], "active": [], "kind": "graph", "directed": true, "chosen": [], "visited": [], "matches": [], "result": 0 }Step 4: Insert trie prefix sh.
State at this checkpoint
{ "values": [ "root", "h", "he", "s", "sh" ], "active": [ 4 ], "kind": "graph", "directed": true, "chosen": [], "visited": [], "matches": [], "result": 0 }Step 8: Compute failure link and inherit suffix outputs.
State at this checkpoint
{ "values": [ "root", "h", "he", "s", "sh", "she" ], "active": [ 5, 2 ], "kind": "graph", "directed": true, "chosen": [], "visited": [], "matches": [], "result": 0 }Step 11: Read h at 2; report terminal and suffix matches.
State at this checkpoint
{ "values": [ "root", "h", "he", "s", "sh", "she" ], "active": [ 4 ], "kind": "graph", "directed": true, "chosen": [], "visited": [], "matches": [ 1, 2 ], "result": 1 }Step 15: Found 4 matches.
State at this checkpoint
{ "values": [ "root", "h", "he", "s", "sh", "she" ], "active": [], "kind": "graph", "directed": true, "chosen": [], "visited": [], "matches": [ 1, 2, 3, 0, 3, 1, 5, 2 ], "result": 4 }
Expected final state
Found 4 matches.
Complexity and input bounds
Family: Strings. Time complexity: O(total pattern length + text length + matches).
Implementation detail: Trie edges show letters and failure edges show fail. The view accepts up to three lowercase patterns with eight letters total. Downloads return inclusive end-index/pattern-ID pairs ordered by end then ID, including overlaps and duplicates.
Space complexity: O(alphabet size times trie nodes) for dense download transitions, plus returned matches and saved frames.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Text 1..24 lowercase letters | 1..3 patterns, each 1..4 letters, eight pattern letters total.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
A terminal node may report several patterns. Duplicate dictionary entries retain distinct IDs. Inherited outputs are essential when a pattern is a suffix of another.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 | // Text n 0..24; 0..3 nonempty patterns of 1..4 letters, at most eight pattern letters total. All letters are lowercase ASCII codes 97..122. Patterns flattened into letters with lengths. Output capacity at least 2*n*patterns; writes [inclusive end index, zero-based pattern ID] pairs sorted by end then ID, including overlaps and duplicate patterns. Returns match count. Dense 26-symbol transitions, BFS failure links and inherited outputs. O(total pattern length + n + matches) for fixed alphabet and bounded pattern count; O(26*nodes + matches) storage including output. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(text, n, letters, lengths, patterns, output) { let next = Array(256).fill(0); let fail = Array(256).fill(0); let mask = Array(256).fill(0); let queue = Array(256).fill(0); let nodes = 1; let offset = 0; let u = 0; let v = 0; let c = 0; let head = 0; let tail = 0; let state = 0; let count = 0; for (let i = 0; i < 256; i++) { next[i] = -1; } for (let p = 0; p < patterns; p++) { u = 0; for (let k = 0; k < lengths[p]; k++) { c = letters[offset]-97; offset++; if (next[u*26+c] == -1) { next[u*26+c] = nodes; nodes++; } u = next[u*26+c]; } mask[u] = mask[u] | (1 << p); } for (c = 0; c < 26; c++) { v = next[c]; if (v == -1) { next[c] = 0; } else { queue[tail] = v; tail++; } } while (head < tail) { u = queue[head]; head++; for (c = 0; c < 26; c++) { v = next[u*26+c]; if (v == -1) { next[u*26+c] = next[fail[u]*26+c]; } else { fail[v] = next[fail[u]*26+c]; mask[v] = mask[v] | mask[fail[v]]; queue[tail] = v; tail++; } } } for (let i = 0; i < n; i++) { state = next[state*26+text[i]-97]; for (let p = 0; p < patterns; p++) { if ((mask[state] & (1 << p)) != 0) { output[count*2] = i; output[count*2+1] = p; count++; } } } return count; } |
Source
Primary research for the matching method. The playground uses bounded ASCII inputs and standalone teaching implementations rather than the original publication program.
- Efficient string matching: An aid to bibliographic search
Alfred V. Aho; Margaret J. Corasick (1975). Original research paper.