28.07Intermediate / Advanced4 topics15 min4 interactive animations

Aho-Corasick preview

A first look at Aho-Corasick: a trie plus failure links that finds all occurrences of many patterns in one pass over the text.

Learning goals

Explain what a failure link points to and why it exists
Build failure links with a breadth-first search
Report every pattern that ends at a text position using dictionary links
View the finished structure as a finite automaton

Prerequisites

Trie fundamentalsBreadth-first searchPrefix and suffix ideas in strings

Searching a text for 1,000 banned words with 1,000 separate searches rereads the text 1,000 times. Aho-Corasick reads it once: the trie follows the letters, and when a letter does not fit, a failure link jumps to the longest suffix that still fits, without going back in the text.

28.07.1

Failure links

Put all patterns in a trie. The **failure link** of a node whose path spells s points to the node for the longest proper suffix of s that is also a path in the trie (the root if there is none). When the next text letter has no edge from the current node, the scan follows the failure link and tries again, so no text letter is ever re-read.

Links are built in breadth-first order, because the link of a node depends on the links of nodes above it: to find the link of the child v of u by letter c, walk up u's failure chain until a node has a c edge. In the preset "Classic: ushers" the node she links to the node he, since he is the longest proper suffix of she that is in the trie.

Java

1static class Node {
2    Node[] next = new Node[26];
3    Node fail, out;                              // failure link; next node on the chain that ends a pattern
4    String word;                                 // the pattern that ends here, if any
5}
6static Node root = new Node();
7static void insert(String pattern) {
8    Node n = root;
9    for (char c : pattern.toCharArray()) {
10        int i = c - 'a';
11        if (n.next[i] == null) n.next[i] = new Node();
12        n = n.next[i];
13    }
14    n.word = pattern;
15}
16static void build() {                            // BFS: failure links
17    Queue<Node> q = new ArrayDeque<>();
18    for (Node c : root.next) if (c != null) { c.fail = root; q.add(c); }
19    while (!q.isEmpty()) {
20        Node u = q.poll();
21        for (int c = 0; c < 26; c++) {
22            Node v = u.next[c];
23            if (v == null) continue;
24            Node f = u.fail;
25            while (f != root && f.next[c] == null) f = f.fail;       // walk back until c can be read
26            v.fail = f.next[c] != null ? f.next[c] : root;
27            v.out = v.fail.word != null ? v.fail : v.fail.out;       // dictionary link
28            q.add(v);
29        }
30    }
31}

Aho-Corasick: failure links and multi-pattern search

Interactive · edit the input

trie of the patterns · 10 nodes

root

word

Current stateFailure targetPattern ends hereNo edge: follow failure linkA pattern ends here

matches

none

Setup

Step 1: put all patterns into one trie. Step 2: give every node a failure link to the longest proper suffix of its path that is also a path in the trie. Step 3: scan the text once, never moving backwards.

Step 1 / 21

Java

1void build() {                                           // BFS: failure links
2    Queue<Node> q = new ArrayDeque<>();
3    for (Node c : root.next) if (c != null) { c.fail = root; q.add(c); }
4    while (!q.isEmpty()) {
5        Node u = q.poll();
6        for (int c = 0; c < 26; c++) {
7            Node v = u.next[c];
8            if (v == null) continue;
9            Node f = u.fail;
10            while (f != root && f.next[c] == null) f = f.fail;    // walk back until c can be read
11            v.fail = f.next[c] != null ? f.next[c] : root;
12            v.out = v.fail.word != null ? v.fail : v.fail.out;    // dictionary link: next pattern ending here
13            q.add(v);
14        }
15    }
16}
17List<String> scan(String text) {
18    List<String> hits = new ArrayList<>();
19    Node n = root;
20    for (int i = 0; i < text.length(); i++) {
21        int c = text.charAt(i) - 'a';
22        while (n != root && n.next[c] == null) n = n.fail;    // follow failure links
23        if (n.next[c] != null) n = n.next[c];
24        for (Node o = n.word != null ? n : n.out; o != null; o = o.out)
25            hits.add(o.word + " ends at " + i);               // every pattern that ends here
26    }
27    return hits;
28}

Live state

0 failure hops0 matches

patterns

No condition evaluated on this step

Execution trace (dry run table)Show 21 steps

Step	Line	State	What happens
1	L1	patterns=4	Step 1: put all patterns into one trie. Step 2: give every node a failure link to the longest proper suffix of its path that is also a path in the trie. Step 3: scan the text once, never moving backwards.
2	L3	node="h" fail=root	Depth-1 node "h": its only proper suffix is the empty string, so the failure link is the root.
3	L3	node="s" fail=root	Depth-1 node "s": its only proper suffix is the empty string, so the failure link is the root.
4	L11	node="he" fail via="root" fail="root" out=none	"he": start from the failure link of its parent ("root"), walk back until a 'e' edge exists. Failure link = root.
5	L11	node="hi" fail via="root" fail="root" out=none	"hi": start from the failure link of its parent ("root"), walk back until a 'i' edge exists. Failure link = root.
6	L11	node="sh" fail via="root" fail="h" out=none	"sh": start from the failure link of its parent ("root"), walk back until a 'h' edge exists. Failure link = "h".
7	L11	node="her" fail via="root" fail="root" out=none	"her": start from the failure link of its parent ("root"), walk back until a 'r' edge exists. Failure link = root.
8	L11	node="his" fail via="root" fail="s" out=none	"his": start from the failure link of its parent ("root"), walk back until a 's' edge exists. Failure link = "s".
9	L11	node="she" fail via="h" fail="he" out="he"	"she": start from the failure link of its parent ("h"), walk back until a 'e' edge exists. Failure link = "he". Dictionary link to "he", a pattern that is a suffix of "she".
10	L11	node="hers" fail via="root" fail="s" out=none	"hers": start from the failure link of its parent ("root"), walk back until a 's' edge exists. Failure link = "s".
11	L23	i=0 char=u state="root"	Read 'u' (position 0): the root has no 'u' edge, so stay at the root.
12	L23	i=1 char=s state="s"	Read 's' (position 1): move to state "s".
13	L23	i=2 char=h state="sh"	Read 'h' (position 2): move to state "sh".
14	L23	i=3 char=e state="she"	Read 'e' (position 3): move to state "she".
15	L25	i=3 pattern="she" start=1	Pattern "she" ends at position 3 (it starts at 1).
16	L25	i=3 pattern="he" start=2	Pattern "he" ends at position 3 (it starts at 2). Reached through a dictionary link.
17	L22	i=4 char=r state="he"	State "she" has no 'r' edge: follow its failure link to "he" without moving in the text.
18	L23	i=4 char=r state="her"	Read 'r' (position 4): move to state "her".
19	L23	i=5 char=s state="hers"	Read 's' (position 5): move to state "hers".
20	L25	i=5 pattern="hers" start=2	Pattern "hers" ends at position 5 (it starts at 2).
21	L27	return=["she@1", "he@2", "hers@2"] failure hops=1	3 matches in 6 characters: she@1, he@2, hers@2 (pattern@start). Text positions advance once each; failure hops total 1 (never more than the characters read), so O(text + patterns + matches).

28.07.2

Dictionary matching

A pattern can end at a text position without being the current node's own word: when scanning ushers, after reading she the matches are she and also he, which is a suffix of she. The **dictionary link** (out) of a node points to the nearest node along its failure chain that ends a pattern, so all matches at a position are found by following out links, with no need to walk the whole failure chain.

Without dictionary links the report loop would walk the entire failure chain at every position, which can be as long as the deepest pattern. With them, each step of the loop reports one real match, so the total work is O(text length + number of matches). The animation lists matches as pattern@start; for ushers they are she@1, he@2 and hers@2.

Java

1static List<String> scan(String text) {          // matches as "pattern@start"
2    List<String> hits = new ArrayList<>();
3    Node n = root;
4    for (int i = 0; i < text.length(); i++) {
5        int c = text.charAt(i) - 'a';
6        while (n != root && n.next[c] == null) n = n.fail;    // follow failure links
7        if (n.next[c] != null) n = n.next[c];
8        for (Node o = n.word != null ? n : n.out; o != null; o = o.out)
9            hits.add(o.word + "@" + (i - o.word.length() + 1));   // every pattern that ends here
10    }
11    return hits;
12}

Aho-Corasick: failure links and multi-pattern search

Interactive · edit the input

trie of the patterns · 10 nodes

root

word

Current stateFailure targetPattern ends hereNo edge: follow failure linkA pattern ends here

matches

none

Setup

Step 1 / 21

Java

1void build() {                                           // BFS: failure links
2    Queue<Node> q = new ArrayDeque<>();
3    for (Node c : root.next) if (c != null) { c.fail = root; q.add(c); }
4    while (!q.isEmpty()) {
5        Node u = q.poll();
6        for (int c = 0; c < 26; c++) {
7            Node v = u.next[c];
8            if (v == null) continue;
9            Node f = u.fail;
10            while (f != root && f.next[c] == null) f = f.fail;    // walk back until c can be read
11            v.fail = f.next[c] != null ? f.next[c] : root;
12            v.out = v.fail.word != null ? v.fail : v.fail.out;    // dictionary link: next pattern ending here
13            q.add(v);
14        }
15    }
16}
17List<String> scan(String text) {
18    List<String> hits = new ArrayList<>();
19    Node n = root;
20    for (int i = 0; i < text.length(); i++) {
21        int c = text.charAt(i) - 'a';
22        while (n != root && n.next[c] == null) n = n.fail;    // follow failure links
23        if (n.next[c] != null) n = n.next[c];
24        for (Node o = n.word != null ? n : n.out; o != null; o = o.out)
25            hits.add(o.word + " ends at " + i);               // every pattern that ends here
26    }
27    return hits;
28}

Live state

0 failure hops0 matches

patterns

No condition evaluated on this step

Execution trace (dry run table)Show 21 steps

Step	Line	State	What happens
1	L1	patterns=4	Step 1: put all patterns into one trie. Step 2: give every node a failure link to the longest proper suffix of its path that is also a path in the trie. Step 3: scan the text once, never moving backwards.
2	L3	node="h" fail=root	Depth-1 node "h": its only proper suffix is the empty string, so the failure link is the root.
3	L3	node="s" fail=root	Depth-1 node "s": its only proper suffix is the empty string, so the failure link is the root.
4	L11	node="he" fail via="root" fail="root" out=none	"he": start from the failure link of its parent ("root"), walk back until a 'e' edge exists. Failure link = root.
5	L11	node="hi" fail via="root" fail="root" out=none	"hi": start from the failure link of its parent ("root"), walk back until a 'i' edge exists. Failure link = root.
6	L11	node="sh" fail via="root" fail="h" out=none	"sh": start from the failure link of its parent ("root"), walk back until a 'h' edge exists. Failure link = "h".
7	L11	node="her" fail via="root" fail="root" out=none	"her": start from the failure link of its parent ("root"), walk back until a 'r' edge exists. Failure link = root.
8	L11	node="his" fail via="root" fail="s" out=none	"his": start from the failure link of its parent ("root"), walk back until a 's' edge exists. Failure link = "s".
9	L11	node="she" fail via="h" fail="he" out="he"	"she": start from the failure link of its parent ("h"), walk back until a 'e' edge exists. Failure link = "he". Dictionary link to "he", a pattern that is a suffix of "she".
10	L11	node="hers" fail via="root" fail="s" out=none	"hers": start from the failure link of its parent ("root"), walk back until a 's' edge exists. Failure link = "s".
11	L23	i=0 char=u state="root"	Read 'u' (position 0): the root has no 'u' edge, so stay at the root.
12	L23	i=1 char=s state="s"	Read 's' (position 1): move to state "s".
13	L23	i=2 char=h state="sh"	Read 'h' (position 2): move to state "sh".
14	L23	i=3 char=e state="she"	Read 'e' (position 3): move to state "she".
15	L25	i=3 pattern="she" start=1	Pattern "she" ends at position 3 (it starts at 1).
16	L25	i=3 pattern="he" start=2	Pattern "he" ends at position 3 (it starts at 2). Reached through a dictionary link.
17	L22	i=4 char=r state="he"	State "she" has no 'r' edge: follow its failure link to "he" without moving in the text.
18	L23	i=4 char=r state="her"	Read 'r' (position 4): move to state "her".
19	L23	i=5 char=s state="hers"	Read 's' (position 5): move to state "hers".
20	L25	i=5 pattern="hers" start=2	Pattern "hers" ends at position 5 (it starts at 2).
21	L27	return=["she@1", "he@2", "hers@2"] failure hops=1	3 matches in 6 characters: she@1, he@2, hers@2 (pattern@start). Text positions advance once each; failure hops total 1 (never more than the characters read), so O(text + patterns + matches).

28.07.3

Multiple-pattern searching

Compare the costs for m patterns of total length P and a text of length n. Searching each pattern separately with a linear algorithm costs O(m × n + P). Aho-Corasick builds the automaton in O(P × alphabet) (or O(P) with sparse transitions) and scans in O(n + z), where z is the number of matches reported. The text is read once, whatever the number of patterns.

The reported matches can be many: a text of aaaa and patterns a, aa, aaa has 4 + 3 + 2 = 9 matches. The function below counts the occurrences of each pattern in one pass, which is how a profanity filter or an intrusion detector reports its findings. Run the preset "Overlapping patterns" (a ab bab bc over ababc): 6 matches from 5 letters.

Java

1static Map<String, Integer> countAll(String text) {      // occurrences of every inserted pattern
2    Map<String, Integer> counts = new TreeMap<>();
3    Node n = root;
4    for (int i = 0; i < text.length(); i++) {
5        int c = text.charAt(i) - 'a';
6        while (n != root && n.next[c] == null) n = n.fail;
7        if (n.next[c] != null) n = n.next[c];
8        for (Node o = n.word != null ? n : n.out; o != null; o = o.out)
9            counts.merge(o.word, 1, Integer::sum);
10    }
11    return counts;
12}

Aho-Corasick: failure links and multi-pattern search

Interactive · edit the input

trie of the patterns · 10 nodes

root

word

Current stateFailure targetPattern ends hereNo edge: follow failure linkA pattern ends here

matches

none

Setup

Step 1 / 21

Java

1void build() {                                           // BFS: failure links
2    Queue<Node> q = new ArrayDeque<>();
3    for (Node c : root.next) if (c != null) { c.fail = root; q.add(c); }
4    while (!q.isEmpty()) {
5        Node u = q.poll();
6        for (int c = 0; c < 26; c++) {
7            Node v = u.next[c];
8            if (v == null) continue;
9            Node f = u.fail;
10            while (f != root && f.next[c] == null) f = f.fail;    // walk back until c can be read
11            v.fail = f.next[c] != null ? f.next[c] : root;
12            v.out = v.fail.word != null ? v.fail : v.fail.out;    // dictionary link: next pattern ending here
13            q.add(v);
14        }
15    }
16}
17List<String> scan(String text) {
18    List<String> hits = new ArrayList<>();
19    Node n = root;
20    for (int i = 0; i < text.length(); i++) {
21        int c = text.charAt(i) - 'a';
22        while (n != root && n.next[c] == null) n = n.fail;    // follow failure links
23        if (n.next[c] != null) n = n.next[c];
24        for (Node o = n.word != null ? n : n.out; o != null; o = o.out)
25            hits.add(o.word + " ends at " + i);               // every pattern that ends here
26    }
27    return hits;
28}

Live state

0 failure hops0 matches

patterns

No condition evaluated on this step

Execution trace (dry run table)Show 21 steps

Step	Line	State	What happens
1	L1	patterns=4	Step 1: put all patterns into one trie. Step 2: give every node a failure link to the longest proper suffix of its path that is also a path in the trie. Step 3: scan the text once, never moving backwards.
2	L3	node="h" fail=root	Depth-1 node "h": its only proper suffix is the empty string, so the failure link is the root.
3	L3	node="s" fail=root	Depth-1 node "s": its only proper suffix is the empty string, so the failure link is the root.
4	L11	node="he" fail via="root" fail="root" out=none	"he": start from the failure link of its parent ("root"), walk back until a 'e' edge exists. Failure link = root.
5	L11	node="hi" fail via="root" fail="root" out=none	"hi": start from the failure link of its parent ("root"), walk back until a 'i' edge exists. Failure link = root.
6	L11	node="sh" fail via="root" fail="h" out=none	"sh": start from the failure link of its parent ("root"), walk back until a 'h' edge exists. Failure link = "h".
7	L11	node="her" fail via="root" fail="root" out=none	"her": start from the failure link of its parent ("root"), walk back until a 'r' edge exists. Failure link = root.
8	L11	node="his" fail via="root" fail="s" out=none	"his": start from the failure link of its parent ("root"), walk back until a 's' edge exists. Failure link = "s".
9	L11	node="she" fail via="h" fail="he" out="he"	"she": start from the failure link of its parent ("h"), walk back until a 'e' edge exists. Failure link = "he". Dictionary link to "he", a pattern that is a suffix of "she".
10	L11	node="hers" fail via="root" fail="s" out=none	"hers": start from the failure link of its parent ("root"), walk back until a 's' edge exists. Failure link = "s".
11	L23	i=0 char=u state="root"	Read 'u' (position 0): the root has no 'u' edge, so stay at the root.
12	L23	i=1 char=s state="s"	Read 's' (position 1): move to state "s".
13	L23	i=2 char=h state="sh"	Read 'h' (position 2): move to state "sh".
14	L23	i=3 char=e state="she"	Read 'e' (position 3): move to state "she".
15	L25	i=3 pattern="she" start=1	Pattern "she" ends at position 3 (it starts at 1).
16	L25	i=3 pattern="he" start=2	Pattern "he" ends at position 3 (it starts at 2). Reached through a dictionary link.
17	L22	i=4 char=r state="he"	State "she" has no 'r' edge: follow its failure link to "he" without moving in the text.
18	L23	i=4 char=r state="her"	Read 'r' (position 4): move to state "her".
19	L23	i=5 char=s state="hers"	Read 's' (position 5): move to state "hers".
20	L25	i=5 pattern="hers" start=2	Pattern "hers" ends at position 5 (it starts at 2).
21	L27	return=["she@1", "he@2", "hers@2"] failure hops=1	3 matches in 6 characters: she@1, he@2, hers@2 (pattern@start). Text positions advance once each; failure hops total 1 (never more than the characters read), so O(text + patterns + matches).

28.07.4

Automaton states

Seen as a machine, the trie nodes are the **states**, the root is the start state, and reading a letter moves to a new state. Following failure links on a mismatch is just a slow way of computing the transition. Precomputing the transition for every state and letter gives a complete table delta[state][letter], after which each text letter costs exactly one array lookup with no loop.

The table is filled in breadth-first order: for a missing edge the transition is the transition of the failure link, delta[u][c] = delta[fail[u]][c], which is already known because the failure link is shallower. The cost is O(states × alphabet) memory, the same trade as array children against a map. The state numbering below follows the breadth-first order, with 0 for the root.

Java

1static int[][] automaton() {                     // delta[state][letter]; state 0 is the root
2    List<Node> order = new ArrayList<>();
3    Map<Node, Integer> id = new HashMap<>();
4    order.add(root);
5    id.put(root, 0);
6    for (int h = 0; h < order.size(); h++)       // breadth-first numbering
7        for (Node v : order.get(h).next)
8            if (v != null) { id.put(v, order.size()); order.add(v); }
9    int[][] delta = new int[order.size()][26];
10    for (int s = 0; s < order.size(); s++) {
11        Node u = order.get(s);
12        for (int c = 0; c < 26; c++) {
13            if (u.next[c] != null) delta[s][c] = id.get(u.next[c]);
14            else delta[s][c] = u == root ? 0 : delta[id.get(u.fail)][c];   // the failure link's transition
15        }
16    }
17    return delta;
18}
19static int countMatches(String text, int[][] delta, int[] matchesAtState) {
20    int state = 0, total = 0;
21    for (char ch : text.toCharArray()) {
22        state = delta[state][ch - 'a'];          // one lookup per letter, no failure loop
23        total += matchesAtState[state];
24    }
25    return total;
26}

Aho-Corasick: failure links and multi-pattern search

Interactive · edit the input

trie of the patterns · 10 nodes

root

word

Current stateFailure targetPattern ends hereNo edge: follow failure linkA pattern ends here

matches

none

Setup

Step 1 / 21

Java

1void build() {                                           // BFS: failure links
2    Queue<Node> q = new ArrayDeque<>();
3    for (Node c : root.next) if (c != null) { c.fail = root; q.add(c); }
4    while (!q.isEmpty()) {
5        Node u = q.poll();
6        for (int c = 0; c < 26; c++) {
7            Node v = u.next[c];
8            if (v == null) continue;
9            Node f = u.fail;
10            while (f != root && f.next[c] == null) f = f.fail;    // walk back until c can be read
11            v.fail = f.next[c] != null ? f.next[c] : root;
12            v.out = v.fail.word != null ? v.fail : v.fail.out;    // dictionary link: next pattern ending here
13            q.add(v);
14        }
15    }
16}
17List<String> scan(String text) {
18    List<String> hits = new ArrayList<>();
19    Node n = root;
20    for (int i = 0; i < text.length(); i++) {
21        int c = text.charAt(i) - 'a';
22        while (n != root && n.next[c] == null) n = n.fail;    // follow failure links
23        if (n.next[c] != null) n = n.next[c];
24        for (Node o = n.word != null ? n : n.out; o != null; o = o.out)
25            hits.add(o.word + " ends at " + i);               // every pattern that ends here
26    }
27    return hits;
28}

Live state

0 failure hops0 matches

patterns

No condition evaluated on this step

Execution trace (dry run table)Show 21 steps

Step	Line	State	What happens
1	L1	patterns=4	Step 1: put all patterns into one trie. Step 2: give every node a failure link to the longest proper suffix of its path that is also a path in the trie. Step 3: scan the text once, never moving backwards.
2	L3	node="h" fail=root	Depth-1 node "h": its only proper suffix is the empty string, so the failure link is the root.
3	L3	node="s" fail=root	Depth-1 node "s": its only proper suffix is the empty string, so the failure link is the root.
4	L11	node="he" fail via="root" fail="root" out=none	"he": start from the failure link of its parent ("root"), walk back until a 'e' edge exists. Failure link = root.
5	L11	node="hi" fail via="root" fail="root" out=none	"hi": start from the failure link of its parent ("root"), walk back until a 'i' edge exists. Failure link = root.
6	L11	node="sh" fail via="root" fail="h" out=none	"sh": start from the failure link of its parent ("root"), walk back until a 'h' edge exists. Failure link = "h".
7	L11	node="her" fail via="root" fail="root" out=none	"her": start from the failure link of its parent ("root"), walk back until a 'r' edge exists. Failure link = root.
8	L11	node="his" fail via="root" fail="s" out=none	"his": start from the failure link of its parent ("root"), walk back until a 's' edge exists. Failure link = "s".
9	L11	node="she" fail via="h" fail="he" out="he"	"she": start from the failure link of its parent ("h"), walk back until a 'e' edge exists. Failure link = "he". Dictionary link to "he", a pattern that is a suffix of "she".
10	L11	node="hers" fail via="root" fail="s" out=none	"hers": start from the failure link of its parent ("root"), walk back until a 's' edge exists. Failure link = "s".
11	L23	i=0 char=u state="root"	Read 'u' (position 0): the root has no 'u' edge, so stay at the root.
12	L23	i=1 char=s state="s"	Read 's' (position 1): move to state "s".
13	L23	i=2 char=h state="sh"	Read 'h' (position 2): move to state "sh".
14	L23	i=3 char=e state="she"	Read 'e' (position 3): move to state "she".
15	L25	i=3 pattern="she" start=1	Pattern "she" ends at position 3 (it starts at 1).
16	L25	i=3 pattern="he" start=2	Pattern "he" ends at position 3 (it starts at 2). Reached through a dictionary link.
17	L22	i=4 char=r state="he"	State "she" has no 'r' edge: follow its failure link to "he" without moving in the text.
18	L23	i=4 char=r state="her"	Read 'r' (position 4): move to state "her".
19	L23	i=5 char=s state="hers"	Read 's' (position 5): move to state "hers".
20	L25	i=5 pattern="hers" start=2	Pattern "hers" ends at position 5 (it starts at 2).
21	L27	return=["she@1", "he@2", "hers@2"] failure hops=1	3 matches in 6 characters: she@1, he@2, hers@2 (pattern@start). Text positions advance once each; failure hops total 1 (never more than the characters read), so O(text + patterns + matches).

Practice ladder

Now try it yourself

Easy

Index Pairs of a String
Implement Trie (Prefix Tree)

Medium

Stream of Characters
Replace Words

Advanced

Substring with Concatenation of All Words
Palindrome Pairs

Key takeaways

A failure link points to the longest proper suffix of a node's path that is also a path in the trie.
Dictionary links skip straight to the next pattern that ends here, so work is proportional to the matches.
Precomputing transitions turns the scan into one table lookup per text letter.