String Matching — Interactive Companion

Interactive visualizations for Chapter 1 of the Advanced Algorithms notes

---

1. Naive String Matching

Slide through every alignment of P against T and see which characters match.

viewof T_naive = Inputs.text({label: "T:", value: "abcaabcabcaab", width: 400})
viewof P_naive = Inputs.text({label: "P:", value: "abcab", width: 400})

viewof step_naive = Inputs.range([0, naive_max_step], {step: 1, value: 0, label: "Step:"})

---

2. KMP — Failure Function (sp values) & Search

Visualize the sp (border) array computation and then step through the KMP search showing how mismatches use the failure function to skip alignments.

Failure Function Table

viewof P_sp = Inputs.text({label: "P:", value: "abcabcab", width: 400})

KMP Search — Step by Step

Watch how KMP uses the failure function to avoid re-scanning characters. The arrow shows where j falls back to on a mismatch.

viewof T_kmp = Inputs.text({label: "T:", value: "abcaabcabcaab", width: 400})
viewof P_kmp = Inputs.text({label: "P:", value: "abcab", width: 400})

viewof step_kmp = Inputs.range([0, kmp_max_step], {step: 1, value: 0, label: "Step:"})

---

3. Z-Algorithm

Visualize the Z-array: Z[k] = length of the longest substring starting at k that matches a prefix of S.

viewof S_z = Inputs.text({label: "S:", value: "aabxaabxcaabxaabxay", width: 500})

viewof step_z = Inputs.range([0, z_max_step], {step: 1, value: 0, label: "Step:"})

---

4. Boyer-Moore — Bad Character Rule

Step through the Boyer-Moore search. The algorithm scans the pattern right-to-left and uses the bad character rule to skip alignments.

viewof T_bm = Inputs.text({label: "T:", value: "abcaabcabcaab", width: 400})
viewof P_bm = Inputs.text({label: "P:", value: "abcab", width: 400})

viewof step_bm = Inputs.range([0, bm_max_step], {step: 1, value: 0, label: "Step:"})

---

5. Suffix Trie & Suffix Tree

Build and visualize the suffix trie and its compacted suffix tree for any input string.

viewof T_tree = Inputs.text({label: "T:", value: "cacao$", width: 300})
viewof tree_view = Inputs.radio(["Suffix Trie", "Suffix Tree"], {value: "Suffix Trie", label: "View:"})

---

6. Algorithm Comparison

Run all algorithms on the same input and compare the number of character comparisons.

viewof T_cmp = Inputs.text({label: "T:", value: "abcaabcabcaab", width: 500})
viewof P_cmp = Inputs.text({label: "P:", value: "abcab", width: 500})

---

7. Keyword Tree — Multiple Pattern Matching

7a. 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
})

---

7b. 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):"})