$./bm-search
text:
pattern:
2 step/s
# algorithm
1BM(t, p) {n = |t|, m = |p|}
2begin
3 pos ← 1
4 while pos ≤ n − m + 1 do
5 i ← m
6 while i > 0 and p[i] = t[pos + i − 1] do i ← i − 1
7 if i = 0 then Output(pos)
8 pos ← pos + D[i]
9 od
10end
# text t with pattern alignment (1-indexed)
no data
# variables
pos
—
i
—
n
20
m
6
t[pos+i-1]
—
p[i]
—
# D array - Good Suffix Shift (precomputed)
no data
# matches found
no data
# current action
enter text and pattern, then click "run" to begin...
# key insight

Boyer-Moore compares the pattern from right to left (i starts at m).

When a mismatch occurs at position i in the pattern, it shifts by D[i] positions.

The D array (good suffix shift) allows skipping positions that cannot match, making the algorithm very efficient in practice.