Noesis
3.8.6 · D5String Algorithms

Question bank — Aho-Corasick — multiple pattern search, automaton

1,646 words7 min read↑ Back to topic
🇮🇳 Yeh page Hinglish mein padho →

True or false — justify

Every node in the trie represents a prefix of at least one pattern.
True. Nodes are created only while inserting patterns, and each node reached is exactly the string spelled from the root, which by construction is a prefix of the pattern being inserted.
The failure link fail[v] can point to a node deeper than v.
False. fail[v] is the longest proper suffix of str(v) that is a node, and a proper suffix is strictly shorter than str(v), so its node has strictly smaller depth.
fail[v] always points to an ancestor of v in the trie.
False. It points to a shorter string, but that string need not lie on v's root path. E.g. with patterns she and he, fail[she] is he, which is on a different branch, not an ancestor of she.
If node v is terminal, then following fail[v] will never reach another terminal.
False. A shorter pattern can be a suffix ending at the same spot — she is terminal and fail[she] = he is also terminal, so both are reported.
The failure link of the root is the root itself.
True (by convention). The root is the empty string; it has no proper suffix that is a shorter node, so it loops to itself, giving the fallback a well-defined base case.
Every child of the root has its failure link equal to the root.
True. A child of the root is a single character; its only proper suffix is the empty string, whose node is the root, so fail = root.
With the full transition table , scanning the text can require following the failure chain at query time.
False. The whole point of precomputing is that failure chasing is absorbed during the BFS build, so each text character is exactly one table lookup.
Aho-Corasick's query time depends on the number of patterns.
False. Query is where is the number of reported matches; the patterns were all baked into one automaton during the build, not re-scanned per query.
If two patterns are identical, the automaton breaks.
False. They merge into the same trie path and the terminal node simply carries both (or one) pattern label; nothing about the failure/transition logic changes.
The transition is the same object as the goto edge go[v][c].
False. go[v][c] is a real trie edge (may not exist); is the completed automaton transition that falls back through fail when no real edge exists, so it is always defined.

Spot the error

"I compute fail[v] by looking only at fail[parent(v)]; I never chain further."
Wrong. If fail[parent] has no child on the edge char c, you must follow fail[fail[parent]], etc., until some node has a c-child or you hit the root. Stopping at one hop can point fail[v] too shallow or to the wrong node.
"I process nodes to compute failure links using DFS (depth-first)."
Wrong ordering. fail[v] may depend on shorter strings (smaller depth) that DFS hasn't finished yet. BFS guarantees all strictly-shorter nodes are done first, so use breadth-first by depth.
"At each text position I check state.isTerminal and report only if true."
Incomplete. Shorter patterns ending as suffixes live on the dictionary/output chain, not on the current node's flag. You must walk the output links (or precomputed dictLink) to catch them all.
"fail[v] should point to a child of the longest-suffix node."
That confuses fail with goto. fail[v] is the node equal to the longest proper suffix of str(v) itself — a completed string, not one character deeper.
"I set δ(v,c) = fail[v] when there's no real edge on c."
Wrong target. The rule is δ(v,c) = δ(fail[v], c) — you jump to the failure link and then take its transition on c, which may itself fall back further. Landing on fail[v] alone drops the character c.
"Since KMP is for one pattern, running KMP once per pattern is basically the same cost as Aho-Corasick."
Wrong. Per-pattern KMP costs where is the pattern count; Aho-Corasick is , removing the factor by scanning once through a shared automaton.
"I built the trie and failure links but skipped the output/dictionary links — matches still report fine."
Only complete-node matches report; suffix matches on the failure chain get missed. You need output links (or on-the-fly failure-chain walking) to report every pattern ending at a position.

Why questions

Why does the current state always represent the longest pattern-prefix that is a suffix of the text read so far?
Because extends a real edge when possible and otherwise falls back to the longest usable suffix; inductively this keeps the state at the maximal matched prefix at every step.
Why can't we just restart at the root on a mismatch instead of using failure links?
Restarting throws away partially matched suffix — after she fails on the next char, he was still a live match, and restarting would miss a pattern like hers that grows from it.
Why is the total failure-chain traversal during scanning bounded, giving amortized per char?
Each character can push the "matched depth" up by at most one, and failure jumps only decrease depth; total decreases total increases , a KMP-style potential argument. (With full this cost is moved entirely into the build.)
Why must failure links point to nodes that are themselves prefixes of some pattern?
Because every node in the trie is a prefix of some pattern by construction; fail[v] targets a node, so its string is automatically a valid pattern-prefix — that's what makes it a legal state to continue from.
Why does BFS order specifically (not any topological order) suffice?
fail[v] always references a strictly shorter string, and depth equals string length in a trie, so ordering by increasing depth (exactly BFS) guarantees dependencies are ready.
Why is the build with a full transition table but with hash maps?
The full table stores a transition for every alphabet symbol at every node ( per node, nodes); maps store only real edges, trading a per-lookup hash cost for total space.
Why does one state sometimes trigger several matches at once?
The output chain links a node to shorter patterns that are suffixes of it (e.g. bc → c); a single position can end multiple nested patterns, so all of them must be emitted.

Edge cases

What happens on a text character that matches no edge from the root?
by convention; the machine stays at the root and simply consumes the char, reporting nothing.
What if a pattern is a single character, like a?
Its terminal node is a direct child of the root; every time the text shows a, lands there (or the output chain passes through it) and a is reported.
What if one pattern is a proper substring of another, like he inside hers?
he sits on the path to hers; whenever matching reaches or passes through he's terminal node — including via output links — he is reported independently of whether hers completes.
What if the pattern set is empty?
The trie is just the root with self-loop transitions on every character; scanning any text lands at the root each step and reports nothing — a valid, degenerate automaton.
What if the text is empty?
The machine starts at the root and takes no steps, so zero matches; build cost is still paid but query is trivially .
What if two patterns share their entire prefix but differ at the last char, like cat and car?
They share the path c → a, then branch to two terminals cat and car; the trie merges the common prefix and each ending stays distinct.
What if a pattern appears multiple times in the text (overlapping)?
Each occurrence is reported separately as the automaton reaches the corresponding state; overlaps are handled naturally because the state already encodes the longest matched suffix at every position.
Recall Quick self-test before moving on

Fail vs goto ::: goto is a real trie edge; fail is a jump to the longest-proper-suffix node. Terminal flag vs output chain ::: flag marks one pattern ending here; output chain finds all shorter patterns ending here too. Why BFS ::: fail always points to a shorter string, ready first when processed by increasing depth. Query cost ::: , independent of the number of patterns.