Naive String Matching

Interactive visualizations for Chapter 1 of the Advanced Algorithms notes

Naive String Matching

Step through every single character comparison. At each shift s, the algorithm compares P[0] vs T[s], then P[1] vs T[s+1], and so on. On a mismatch it backtracks to the next shift and starts over from P[0] — this is the repeated work that makes the naive approach slow.

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