Keyword Tree — Multiple Pattern Matching

Interactive visualizations for Chapter 1 of the Advanced Algorithms notes

Building the Keyword Tree

Enter a comma-separated list of patterns and see the resulting keyword tree. The stats panel shows size (number of edges), height (longest pattern), and maximum fan-out.

viewof patterns_input = Inputs.text({
  label: "Patterns (comma-separated):",
  value: "potato, tatoo, theater, other",
  width: 500
})

Searching with the Keyword Tree

Enter a text and patterns. Step through each starting position to see the descent from the root: active edges light up, non-matching branches are grayed out.

viewof T_kw_search = Inputs.text({
  label: "T:",
  value: "a]potato that was put in a theater",
  width: 500
})
viewof P_kw_search = Inputs.text({
  label: "Patterns (comma-separated):",
  value: "potato, tatoo, theater, other",
  width: 500
})

viewof step_kw = Inputs.range([0, kw_max_step], {step: 1, value: 0, label: "Step (starting position):"})

---

Aho-Corasick: Failure Links & Output Links

The keyword tree alone restarts from the root at every position. The Aho-Corasick automaton adds two types of pointers:

• Failure links (red dashed): when the descent gets stuck, jump to the longest proper suffix of the current path that is also a prefix of some pattern.
• Output links (green dotted): chain together all patterns that end along the failure-link path, so patterns ending at internal nodes are not missed.

viewof P_ac = Inputs.text({
  label: "Patterns (comma-separated):",
  value: "he, she, his, hers",
  width: 500
})