AA-VIZ /

String Matching

Naive KMP ↳ visualizer Z-Algorithm Boyer-Moore Suffix Structures Comparison Keyword Tree Rabin-Karp Shift-And

Rabin-Karp

Interactive visualizations for Chapter 1 of the Advanced Algorithms notes

Rabin-Karp — Rolling Hash Search

Step through the Rabin-Karp algorithm. At each window position, the fingerprint (hash mod q) of the current window is compared against the pattern’s fingerprint:

• Orange window = no hash match → skip instantly
• Purple window = hash hit → must verify character-by-character
• Green window = verified true match
• Red window = spurious hit (hash matched but characters differ)

Try small values of q (e.g. 3, 5) to see spurious hits in action.

viewof T_rk = Inputs.text({label: "T:", value: "abracadabra", width: 400})
viewof P_rk = Inputs.text({label: "P:", value: "abra", width: 400})
viewof q_rk = Inputs.range([2, 997], {step: 1, value: 101, label: "q (prime):"})

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

Effect of q on Spurious Hits

The bar chart below compares four values of q on the same input. Small q → many spurious hits (red bars). Large prime q → almost none.