Foundations — Aho-Corasick — multiple pattern search, automaton

Before you climb into the main note, you must own the vocabulary it speaks. We build it one brick at a time.

0 · The raw material — strings, characters, and the alphabet

Everything here is about text: a row of symbols read left to right.

Why the symbol $\Sigma$? Because later, cost formulas count "one slot per possible next letter", and that number of slots is $|\Sigma |$. Naming the alphabet lets us talk about that cost.

Look at the figure: a string is just cells in a line, each cell holding one character. The little index numbers under the cells will matter the moment we talk about positions — "the match ended at position 4".

1 · Prefix and suffix — the two halves that make everything work

These two words are the heart of the whole algorithm. Get them wrong and nothing else lands.

Why does Aho-Corasick obsess over these? Because the machine's whole job is:

"The longest prefix of some search word that is also a suffix of the text I've read so far."

That single sentence uses both concepts at once. When a letter fails to extend a match, the "shortcut rope" jumps you to the longest proper suffix of where you were that is still a prefix of some word. Both halves, again. Hold onto this — it returns in Step 2 of the parent note.

2 · Set, and $\sum |p_i|$ — measuring a whole dictionary

We do not search for one word; we search for a dictionary of words at once.

Why do we need $M$? Because the build cost of the machine is measured in $M$ (and $|\Sigma |$), not in "number of patterns". Two patterns of length 1000 cost the same to build as 2000 patterns of length 1 — what matters is total characters. Naming $M$ lets the complexity line say that precisely.

3 · Graphs, nodes, edges — the shape of the machine

The machine is a graph. If that word scares you, it is just dots joined by arrows.

Why a tree and not a plain list? Because words that start the same (he and hers both start he) can share their front edges, so the machine stores he once. That sharing is exactly what a tree gives you and a list does not.

4 · The trie — a tree of prefixes

Now combine "tree" with "prefix" and you get the first real structure.

We go deeper on the trie itself in Trie — prefix tree; here you only need: node = a prefix, edge = a character, terminal = a word ends.

We name three operations on it, matching the parent note:

• $\text{str}(v)$ = the string that node $v$ stands for.
• $\text{go}[v][c]$ or $\text{child}(v,c)$ = the node you reach from $v$ by following the real edge labeled $c$ (may not exist).
• terminal: a node flagged because a full pattern ends there.

5 · The failure link — the "shortcut rope"

This is the one genuinely new idea; the parent note derives it fully. Here we only make sure the symbol and picture are clear.

That "always shorter / always higher" fact is why we build failure links in a specific order — see the next brick.

This idea is borrowed directly from single-pattern matching. If you have seen KMP — single pattern matching, the failure link is exactly KMP's prefix function, but spread over a whole tree of words instead of one word.

6 · BFS — processing shortest strings first

To fill in every failure link correctly, we must visit nodes in order of depth. The tool that does that is BFS.

7 · The automaton and its transition $\delta$

Finally, the word in the topic title: automaton.

There is a whole family of string machines built on suffixes rather than a fixed dictionary — see Suffix Automaton and Suffix Tree — and other matching engines like the Z-algorithm and string matching. Aho-Corasick is the "many fixed patterns at once" specialist.

8 · The cost symbols — $n$, $M$, $\Sigma$, $z$, and big-$O$

Last brick: the letters in the complexity line, so it reads as English.

Prerequisite map

Read it upward: characters make strings; strings give prefixes/suffixes and a dictionary; graphs give trees, trees give the trie; prefix + suffix + BFS give failure links; trie + failure links give the automaton; add the cost symbols and you have the full Aho-Corasick machine.

Equipment checklist

Cover the right side and answer aloud; if any stalls, reread that section before the main note.