AA-VIZ /

String Matching

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

Shift-And Algorithm

Interactive visualizations for Chapter 1 of the Advanced Algorithms notes

Alphabet masks

Before running the algorithm, we pre-compute one bit vector per alphabet character. \(U_x[i] = 1\) if and only if \(P[i] = x\). These masks are the ingredient that encodes the pattern into the bit-parallel framework.

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

Shift-And — step by step

The algorithm processes \(T\) left to right. At each position \(j\) it updates a single bit vector \(M\) (one column of the dynamic programming matrix) using:

\[M_j = ((M_{j-1} \ll 1) \mid 1) \;\&\; U_{T[j]}\]

The bit at position \(i\) of \(M_j\) tells us: “the prefix \(P[0..i]\) is a suffix of \(T[0..j]\).” When the last bit (position \(m{-}1\)) is 1, we have found a full occurrence of \(P\).

Use the slider to step through the algorithm one text position at a time. The top section shows the DP matrix filling column by column; the bottom section shows the bit-vector operations in detail.

viewof T_sa = Inputs.text({label: "T:", value: "cacacaocacao", width: 400})
viewof P_sa = Inputs.text({label: "P:", value: "cacao", width: 400})

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

Comparison count

How many bit-level operations does the Shift-And algorithm need? Each text position requires exactly one shift, one OR, and one AND — all on a single machine word. Move the slider to see the total count grow linearly with \(|T|\).