KMP — Failure Function & Search

Interactive visualizations for Chapter 1 of the Advanced Algorithms notes

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