$./rabin-karp
text:
pattern:
q:
2 step/s
# algorithm
1RabinKarp(t, p, q) {n = |t|, m = |p|, d = |Σ|}
2begin
3 h ← d^(m-1) mod q
4 p̄ ← t̄₀ ← 0
5 for i ← 1 to m do ▷ Preprocessing
6 p̄ ← (d p̄ + p[i]) mod q
7 t̄₀ ← (d t̄₀ + t[i]) mod q
8 od
9 for j ← 0 to n-m do ▷ Searching
10 if p̄ = t̄ⱼ then if p[1..m] = t[j+1..j+m] then Output(j)
11 if j < n-m then t̄ⱼ₊₁ ← (d(t̄ⱼ - t[j+1]h) + t[j+m+1]) mod q
12 od
13end
# text t (0-indexed)
no data
# pattern p (0-indexed)
no data
# variables
n
11
m
4
q
101
h
—
p̄
—
t̄ⱼ
—
j
—
i
—
hash match
✗
string match
✗
# hash comparison
no data
# current action
enter text and pattern, then click "run" to begin...
# matches found
no data
# rolling hash formula
t̄ⱼ₊₁ = (d(t̄ⱼ - t[j+1]×h) + t[j+m+1]) mod q
Remove leftmost char contribution, shift left (×d), add new rightmost char