Exercises — Aho-Corasick — multiple pattern search, automaton

• str(v): the string spelled from root to $v$.
• fail[v]: the node for the longest proper suffix of str(v) that is still a node (a pattern prefix).
• δ(v,c): where reading c takes you — the real child if it exists, otherwise δ(fail[v], c).
• Dictionary chain: the sequence of terminal nodes found by following fail links up from $v$; all report a match ending here.

A string is a node iff it is a prefix of some pattern.

• h ✓ (prefix of he, his, hers)
• sh ✓ (prefix of she)
• her ✓ (prefix of hers)
• hi ✓ (prefix of his)
• sha ✗ (no pattern starts sha)
• e ✗ (no pattern starts with e; note "e" appears in "he" but is not a prefix)

str(bab) = "bab", parent p = ba via character b. We want the longest proper suffix of "bab" that is a node. Proper suffixes ending in the last char b: "ab", "b", "" (plus c-check). Walk the failure chain of p = ba, looking for a child on b:

• fail[ba] = longest proper suffix of "ba" that is a node = "a" (node ✓). Does node a have a child on b? Yes: a → ab. Stop.
• So fail[bab] = ab. Check: "ab" is indeed the longest proper suffix of "bab" that is a node. ✓

Matches (grouped by end position, longest-first within a position): a (pos 1), ab (pos 2), bc, c (pos 3), c (pos 4).

After landing at node bc (a terminal), the dictionary chain is bc → fail[bc] = c → fail[c] = root. Node c is also terminal, so it fires too. Both patterns end at that same text position, one being a suffix of the other. The dictLink[bc] shortcut points straight from bc to c, letting us emit both without visiting non-terminal nodes.

Recall $\text{depth}(v)=|\text{str}(v)|$ (defined at the top of this page): the number of characters in the string spelled from the root to $v$. Now fail[v] is a proper suffix of str(v), so |str(fail[v])| < |str(v)|, hence $\text{depth}(\text{fail}[v])<\text{depth}(v)$ — strictly smaller. Therefore when BFS reaches depth $d$, every node of depth $<d$ (including all fail targets it needs) is already finalized. This is exactly why we compute fail in breadth-first order and not recursively.

Define a potential = current $\text{depth}$ of the state. Each read of a text character increases depth by at most $1$ (one downward edge), so over $n$ characters depth rises by at most $n$ total. Every failure jump decreases depth by at least $1$. Since depth starts at $0$, stays $\ge 0$, and only rises $n$ times total, the number of failure jumps summed over the entire scan is $\le n$. Hence all the jumping is $O(n)$ amortized — no single step's cost matters, only the total. (With the full δ table each character is even simpler: one $O(1)$ lookup.) The extra $z$ is unavoidable: you must spend time emitting each of the $z$ matches.

str(hers) = "hers". Longest proper suffix of "hers" that is a node: check "ers" (✗), "rs" (✗), "s" (✓ node). Any longer suffix that is a node? "ers", "rs" are not prefixes of any pattern. So fail[hers] = s. The student is correct. (Trap defused: many expect a fancier target, but s genuinely is the longest matching suffix here.)

Nodes (as strings): root, a, ab(✓ab), b, ba(✓ba), bab(✓bab). Compute fail in BFS (increasing depth):

• depth 1: fail[a]=root, fail[b]=root (root's children fail to root).
• depth 2:
  • fail[ab]: parent a, char b. Walk fail[a]=root; root child on b? yes b. So fail[ab]=b.
  • fail[ba]: parent b, char a. Walk fail[b]=root; root child on a? yes a. So fail[ba]=a.
• depth 3:
  • fail[bab]: parent ba, char b. Walk fail[ba]=a; node a child on b? yes ab. So fail[bab]=ab. This matches the plum arrows in the figure above.

Matches grouped by end position (longest-first): ba(pos 2), bab, ab(pos 3), ba(pos 4), bab, ab(pos 5).

Take {c, bc, abc}. Scan text abc.

• a → node a (no report), because root has real edge a
• b → ab? real edge exists → ab (no report)
• c → abc (✓abc), because ab has real edge c. Dictionary chain: abc → fail = bc (✓) → fail = c (✓) → root. At the final c, three patterns fire: abc, bc, c — each a suffix of the previous. Position: index 3 (last char).

• KMP-per-pattern total cost: $O(M+mn+z)$ — building all prefix functions is $O(M)$, each of the $m$ patterns scans the whole text ($mn$), plus reporting $z$.
• Aho-Corasick: build $O(M\Sigma )$ (full table), scan $O(n+z)$; total $O(M\Sigma +n+z)$. Precise criterion. Aho-Corasick is asymptotically cheaper exactly when its total is smaller: $M\Sigma +n+z<M+mn+z⟺M\Sigma +n<M+mn.$ Rearranging (the $z$ terms cancel): $M(\Sigma -1)<(m-1)n⟺n>\frac{M(\Sigma -1)}{m-1}(\text{for }m\ge 2).$ So for any $m\ge 2$, Aho-Corasick wins once the text is longer than $\frac{M(\Sigma -1)}{m-1}$. As $m$ grows this threshold shrinks, and with maps (build $O(M)$, so the $M\Sigma$ term becomes $M$) the condition relaxes to simply $n>0$ whenever $m\ge 2$.

Naive quadratic family: patterns {a, aa, aaa, …, a^k} (all prefixes of aⁿ), text aⁿ. At text position $i$, the state is node a^i, and its failure chain is a^i → a^{i-1} → … → a → root. To emit outputs the naive walk visits every node on the chain, costing $\Theta (i)$ at position $i$, and ${\sum }_{i=1}^{n}i=\Theta (n^2)$ — quadratic. The dictLink fix: dictLink[v] = the nearest terminal node strictly above $v$ on the failure chain. Emitting then hops only from one reported match to the next terminal, so the emit work is proportional to the number of matches $z$ plus $O(1)$ per character, giving $O(n+z)$. The key: never touch a non-terminal node during output.

(a) Nodes: root, a, ab(✓ab), aba(✓aba), b, ba(✓ba), bab(✓bab). Fail (BFS):

• fail[a]=root, fail[b]=root
• fail[ab]: parent a,b; fail[a]=root, root child b → fail[ab]=b
• fail[ba]: parent b,a; fail[b]=root, root child a → fail[ba]=a
• fail[aba]: parent ab,a; fail[ab]=b, b child a? yes ba → fail[aba]=ba
• fail[bab]: parent ba,b; fail[ba]=a, a child b? yes ab → fail[bab]=ab

(b) Full δ — each cell says whether a real edge exists, else recurses via fail:

Correction on δ(aba,b): aba has no real b-edge, so δ(aba,b)=δ(fail[aba]=ba, b)=bab (ba has real edge b). And δ(bab,a): bab has no real a-edge, so δ(bab,a)=δ(fail[bab]=ab, a)=aba (ab has real edge a).

(c) Scan ababa:

Careful re-scan (using the full δ table):

• a: root→a. reports: none.
• b: a real edge b → ab. reports: ab.
• a: ab real edge a → aba. reports aba; dictLink[aba]=ba → ba.
• b: aba no b-edge → δ(aba,b)=bab. reports bab; dictLink[bab]=ab → ab.
• a: bab no a-edge → δ(bab,a)=aba. reports aba; dictLink[aba]=ba → ba.

Matches grouped by end position (longest-first): ab(pos 2), aba, ba(pos 3), bab, ab(pos 4), aba, ba(pos 5).

Did you, for every problem, (1) confirm each claimed node is a real prefix, (2) verify $\text{depth}(\text{fail}[v])<\text{depth}(v)$, (3) follow the dictionary chain (or dictLink) for output not just the terminal flag, and (4) build fail/δ in BFS order? If yes, you have mastered the mechanics.